92. Reverse Linked List II --- M

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:

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

Example 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?

A:

/**
 * 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) {
        ListNode header(0, head);
        auto tail1 = &header;
        for(int i =0; i<left-1; i++){
            tail1 = tail1->next;
        }
        ListNode newHeader(0, tail1->next);
        auto runner = newHeader.next;
        auto tail2 = newHeader.next;
        for(int i = left; i<= right; i++){
            auto tmp = runner;
            runner = runner->next;
            tmp->next = newHeader.next;
            newHeader.next = tmp;
        }
        tail2->next = runner;
        tail1->next = newHeader.next;
        return header.next;
    }
};




Mistakes:
1:  没有考虑从头结点开始reverse的时候， preNode 会是什么情况。

 ------ 解决方法-------自己加了一个header 结点。

2： 虽然是从m...n 这些个位置，但是由于我们是把一个个的，detach，然后插到最前面。  因此， 不需要 detach 第一个 m的位置。---------这样就避免了null pointer exception。

3：考虑到有可能第一个node也被reverse了， 我们就不能直接返回开始的head， 而应该返回header.next。 



Learned: