092.ReverseLinkedListII.md

tags: Linked List

#[LeetCode 92] Reverse Linked List II Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Diffculty
Medium

Similar Problems
[LeetCode 206] Reverse Linked List Easy

Analysis

对于链表的很多操作，都可以通过 dummy node 来增加便利，这题也一样，把 dummy node 指向原链表的头结点，这样的话就算头结点变动了，我们还是可以通过 dummy->next 来获得新链表的头结点。

反转部分节点，主要可以分三步

1. 找到 m 节点的前一个指针 pre（加个 safe guard 可避免头指针的问题）
2. 从 m 节点开始往后 reverse n 个节点（通过双指针来实现），用一个 front 指针指向这个 reverse 后的链表
3. 合并 pre 链表，front 链表及 post 链表。

这道题的要求是只通过一次遍历完成，就拿题目中的例子来说，变换的是 2, 3, 4 这三个点，那么我们可以先取出 2 ，用 front 指针指向 2 ，然后当取出 3 的时候，我们把 3 加到 2 的前面，把 front 指针前移到 3 ，依次类推，到 4 后停止，这样我们得到一个新链表 4->3->2 , front 指针指向 4。对于原链表来说，有两个点的位置很重要，需要用指针记录下来，分别是 1 和 5，因为当 2, 3, 4 被取走时，原链表就变成了 1->5->NULL，要把新链表插入的时候需要这两个点的位置。1 的位置很好找，因为知道 m 的值，我们用 pre 指针记录 1 的位置，5 的位置最后才能记录，当 4结点被取走后，5 的位置需要记下来，这样我们就可以把倒置后的那一小段链表加入到原链表中。

1 -> 2 -> 3 -> 4 -> 5 -> NULL
1 -> 2 <- 3 <- 4 <- 5 -> NULL
1 -> 4 -> 3 -> 2 -> 5 -> NULL

头插法

技巧在于记录下这么几个变量：dummyHead、子链反转前的头节点，子链反转前头节点前面一个节点，子链反转过程中的当前节点，子链反转过程中的下一个节点，这五个指针。先跳过前 m 个节点，然后初始化好这五个指针后，用 I 中的方法反转链表。完成了第 n 个节点的反转后，将子链反转前的头节点的 next 设为子链反转过程中的下一个节点，将子链反转前头节点前面一个节点的 next 设为子链反转过程中的当前节点。由于设置了 dummyhead，我们所有的反转操作都是不包含头节点的，所以直接返回 dummyhead.next 就行了。

Solutions

解法一

class Solution {
public:
    ListNode* reverseBetween(ListNode *head, int m, int n) {
        ListNode newhead(-1);
        newhead.next = head;
        
        if(head == nullptr || head->next == nullptr)
            return newhead.next;
            
        ListNode *startpoint = &newhead; // startpoint 指向需要开始 reverse 的前一个
        ListNode *node1 = nullptr;         // 需要 reverse 到后面去的节点
        ListNode *node2 = nullptr;         // 需要 reverse 到前面去的节点
        
        for (int i = 0; i < n; i++) {
            if (i < m-1){
                startpoint = startpoint->next; // 找真正的startpoint
            } else if (i == m-1) {            // 开始第一轮
                node1 = startpoint->next;
                node2 = node1->next;
            }else {
                node1->next = node2->next;      // node1 交换到 node2 的后面
                node2->next = startpoint->next; // node2 交换到最开始
                startpoint->next = node2;       // node2 作为新的点
                node2 = node1->next;            // node2 回归到 node1 的下一个，继续遍历
            }
        }
        return newhead.next;
    }
};

解法二

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *newHead = new ListNode(-1);
        newHead->next = head;
        ListNode* prev = newHead;
        for(auto i = 0 ; i < m-1 ; i++) { // 移动到第 m 个节点的前一个节点
            prev = prev->next;
        }
        ListNode* const reversedPrev = prev; 
        //position m
        prev = prev->next;                // pre 移动到要反转的第一个节点
        ListNode* cur = prev->next;       // cur 移动到要反转的第二个节点，将其与 pre 反转
        for(auto i = m ; i < n ; i++){
            prev->next = cur->next;
            cur->next = reversedPrev->next;
            reversedPrev->next = cur;
            cur = prev->next;
        }
        return newHead->next;
    }
};

解法三

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = dummy;
        ListNode *pre, *front, *last;
        for (int i = 1; i <= m - 1; ++i) // 移动到第 m 个节点的前一个节点
            cur = cur->next;
        pre = cur;
        last = cur->next;   // cur->next 就是要反转的第一个节点，反转之后就成尾部了，因此在这里标记之

        ListNode *prev = pre->next;
        for (int i = m; i <= n; ++i) {
            cur = pre->next;
            pre->next = cur->next;
            cur->next = front;
            front = cur;
        }
        cur = pre->next;
        pre->next = front;
        last->next = cur;
        return dummy->next;
    }
};