92. Reverse Linked List II

标签： leetcode list

Qustion

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.

关键：抓住变化的那个结点,以及注意循环次数，防止访问NULL地址

解题思路

1. 定位到前结点nodePre
2. 记录要插入的最前面的结点childListBegin，和revert list的最后一个结点childListEnd
3. 在这两处进行操作

    nodeA = childListEnd->next;
    childListEnd->next = nodeA->next;
    nodeA->next = childListBegin;
    childListBegin = nodeA;

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (!head) return head;
        if (m == n) return head;

        ListNode *childListBegin, *childListEnd, *nodeA, *nodeB, *nodePre;

        for (int i = 0, nodePre = NULL; i < m - 2; ++i)
        {
            nodePre = nodePre->next;
        }

        nodeA = (nodePre) ? nodePre->next : head;
        nodeB = nodeA->next;

        nodeA->next = nodeB->next;
        nodeB->next = nodeA;

        childListBegin = nodeB;
        childListEnd = nodeA;

        int count = n - m;
        for (int i = 0; i <  count - 1; ++i)
        {
            nodeA = childListEnd->next;
            childListEnd->next = nodeA->next;
            nodeA->next = childListBegin;
            childListBegin = nodeA;
        }

        if (nodePre)
        {
            nodePre->next = childListBegin;
        }
        
        if (m == 1) {
            return childListBegin;
        }
        
        return head;
    }
};