92.Reverse Linked List II

Tags: Medium Link List

Link: https://leetcode.com/problems/reverse-linked-list-ii/

---

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

---

Example:

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

---

Answer:

/**
 * 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) {
        ListNode *dummy = new ListNode(0), *head2;
        dummy -> next = head;
        head2 = dummy;

        for(int i = 0; i < m - 1; ++i)
        {
            head2 = head2 -> next;
        }
        ListNode *pre = head2 -> next, *cur = pre -> next;

        for(int i=0; i < n - m; ++i)
        {
            pre -> next = cur -> next;
            cur -> next = head2 -> next;
            head2 -> next = cur;
            cur = pre -> next;
        }

        return dummy -> next;
    }
};

解析：

此题和206题的reverse link list差不多，思路仍然是增加一个head，pre和cur，反转部分的操作不变。区别在于需要先把head2定位到需要反转的位置的前一个元素。