92. Reverse Linked List II

Posted on Edited on In

92. Reverse Linked List II

Description

Difficulty: Medium

Related Topics: Linked List

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

1
2
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

1
2
Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Follow up: Could you do it in one pass?

Hints/Notes

  • Implement reverseN(reverse the fist N elements of one list) first,
    i.e. reverseN(3) = 3->2->1->4->5
1
2
3
4
5
6
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        return nullptr;
    }
}

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        head->next = reverseBetween(head->next, left - 1, right - 1);
        return head;
    }

    ListNode* reverseN(ListNode* head, int n) {
        if (n == 1) {
            succesor = head->next;
            return head;
        }
        ListNode* tmpHead = reverseN(head->next, n - 1);
        head->next->next = head;
        // in fact, this step is only useful for the first node
        head->next = succesor;
        return tmpHead;
    }

    ListNode* succesor = nullptr;
};