Reverse Linked List II Problem


Description

LeetCode Problem 92. Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list.

Example:

1
2
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL


Solution

This problem is similar to the reverse linked list problem. The difference is we only need to reverse the nodes from position m to n.

We can iterate through the list. When we reach the m-1th node, we use a pointer (head_r) to record this node. This pointer will point to the head node of the reversed sub list, or will be the head node of the reversed sub list (for the m = 1 case).

When we reach the mth node, we also use a pointer (tail_r) to record this node. This will be the tail node of the reversed sub list. We also start reversing the list from this node. We can use the same method in the reverse linked list problem.

When we reach the nth node, we finish reversing the list. We then point the tail_r pointer to the n+1th node, and point the head_r pointer to the nth node. In this way, we can reverse the sub list in place.

We also need to handle the case (m = 1) carefully. In this case, we set head_r node to be the nth node, and return head_r node as the head node of the new list.

The time complexity of the approach is O(n), and the space complexity is O(1).


Sample C++ Code

This is a C++ implementation of the above approach.

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <algorithm>

using namespace std;

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) {}
};

ListNode* reverseBetween(ListNode* head, int m, int n) {
    if ((head == NULL) || (head->next == NULL))
        return head;
    if (m == n)
        return head;
    
    int i = 1;
    ListNode* curr = head;
    ListNode* prev = NULL;
    ListNode* tmp;
    ListNode* tail_r;
    ListNode* head_r = NULL;
    while (curr != NULL) {
        if ((i >= m) && (i <= n)) {
            if (i == m) {
                tail_r = curr;
            }
            if (i == n) {
                tail_r->next = curr->next; 
                if (head_r == NULL) {
                    head_r = curr;
                } else {
                    head_r->next = curr;
                }
            }
            tmp = curr;
            curr = curr->next;
            tmp->next = prev;
            prev = tmp;
            i ++;
        } else {
            if (i == m - 1)
                head_r = curr;
            i ++;
            prev = curr;
            curr = curr->next;
        }
    }
    if (m == 1)
        return head_r;
    else
        return head;
}

int main() {
    ListNode* lhead = new ListNode(1);
    ListNode* curr = lhead;
    curr->next = new ListNode(2);
    curr = curr->next;
    curr->next = new ListNode(3);
    curr = curr->next;
    curr->next = new ListNode(4);
    curr = curr->next;
    curr->next = new ListNode(5);

    int m = 2, n = 4;

    ListNode* head = reverseBetween(lhead, m, n);
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    return 0;
}




Related Posts

Intersection Of Two Linked Lists Problem

LeetCode 160. Given the heads of two singly linked-lists headA...

Sort List Problem

LeetCode 148. Given the head of a linked list, return...

Reorder List Problem

LeetCode 143. You are given the head of a singly...

Linked List Cycle Problem

LeetCode 141. Given head, the head of a linked list,...

Linked List Cycle II Problem

LeetCode 142. Given the head of a linked list, return...

Insertion Sort List Problem

LeetCode 147. Given the head of a singly linked list,...