leetcode解题: Reverse Linked List II (92)

发表于 | 分类于

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.

解法1：Two pointers, One Pass O(N)

题目要求只能走一遍，所以考虑用双指针。同时需要考虑到的是，等reverse结束，我们的head是不确定的，在这种情况下我们考虑使用dummy node，将dummy node指向head，最后不管其中怎么变化，我们一定是返回dummy.next
假设我们已经知道从node m 到node n需要reverse，那么reverse之后由于要并入原来的list，我们需要知道子list的head之前的那个node，以及子list的尾巴之后的那个node， 比如：
1->2->3->4->5, if m = 2, n = 4
那么我们需要记录指针位置1和指针位置5，当把2->3->4翻转过后把新的head和tail指向这两个节点就可以了。
实现上维护two pointers和一个计数器，当right pointer移动到子list的head的时候，left pointer就自然而然的指向了前面的那个node，把子list的head记录为newtail，因为当reverse之后他会变成tail。
然后开始reverse的过程，同时变更计数器，直到计数器等于n的值为止。这个时候我们就得到了新的head，记录下一个值便是我们要将newtail指向的位置。最后返回dummy.next
C++

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
/**
 * 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 (m == n) {
            return head;
        }
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* ptr0 = dummy;
        ListNode* newhead = NULL;
        ListNode* newtail = NULL;
        int count = 1;
        while (count < m) {
            ptr0 = ptr0->next;
            head = head->next;
            ++count;
        }
        newtail = head;
        ListNode* prev = head;
        head = head->next;
        ++count;
        while (count <= n) {
            ListNode* temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
            ++count;
        }
        newhead = prev;
        ptr0->next = newhead;
        newtail->next = head;
        return dummy->next;
    }
};

Java

1

解法2：Two pointers, One Pass O(N)

解法1的思想比较直观，不过写起来比较繁琐。从discuss上看来的这个解法比较简洁。要注意的是其中有把一个子list反转的template需要记一下，很有用。

1
prev->A->B->C->res

对于上面这个list，要反转A到C，那么设start为A，then为B两个指针。
prev不移动而移动start和then，每一次把start向后移动一位，并且把then指向的node接到prev之后就可以达到效果。
代码是

1
2
3
4
5
6
for (int i = 0; i < n - ml; i++) {
  start.next = then.next;
  then.next = prev.next;
  prev.next = then;
  then = start.next;
}

完整的代码就简洁多了。
Java

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n || head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
        }
        // prev points to the m nodes
        ListNode start = prev.next;
        ListNode then = start.next;
        for (int i = 0; i < n - m; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return dummy.next;
    }
}