leetcode92.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.

将链表中从第m个节点开始翻转至第n个节点结束。要求在第一次遍历中即完成该过程。

思路一：管他的一次遍历

直观点想，我们只需要知道开始翻转的第一个节点和需要翻转的最后一个节点。将从第一个该节点开始依次插入最后一个节点后面直到遇到最后一个节点。该算法的时间复杂度为O(2n-m),即O(n+n-m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode reverseBetween(ListNode head, int m, int n) {
    if(m==n) return head;
    ListNode dummy1 = new ListNode(0), dummy2 = new ListNode(0), start = new ListNode(0);
    dummy1.next = head;
    dummy2.next = head;
    start.next = dummy2;
    for(int i = 0 ; i <n-m+1 ; i++){
        dummy1 = dummy1.next;
    }
    for(int i = 0; i<m-1 ; i++){
        dummy1 = dummy1.next;
        dummy2 = dummy2.next;
    }
    while(dummy2.next != dummy1){
        ListNode temp = new ListNode(dummy2.next.val);
        dummy2.next = dummy2.next.next;
        temp.next = dummy1.next;
        dummy1.next = temp;
    }
    return start.next.next;
}

思路二：one pass

那么有没有办法正向翻转呢。当然是可以的啦，换句话说，我们只要将节点不断往前插入就行啦。举题中的例子。1->2->3->4->5->NULL, m = 2 n = 4,
首先我们将数值3提取出来插入到1和2之间1-3-2-4-5
之后将数值4提取出来插入到1和2之间1-4-3-2-5
至此翻转结束。
也就是说我们在这个过程中需要知道3个节点，开始翻转的前一个节点prev，开始翻转的节点start，以及插入到前面的这个节点then。
最后我们还需要一个dummy节点来标记整个链表的起始节点。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode reverseBetween2(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;
    }
    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;
}