Thursday, November 20, 2014

[LeetCode] 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->NULLm = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

思路:

反转整个链表的变种,指定了起点和终点。由于m=1时会变动头节点,所以加入一个dummy头节点

1. 找到原链表中第m-1个节点start:反转后的部分将接回改节点后。
从dummy开始移动m-1步

D->1->2->3->4->5->NULL
       |
      st

2. 将从p = start->next开始,长度为L = n-m+1的部分链表反转。
            __________
            |                  |
            |                 V
D->1->2<-3<-4    5->NULL             
       |     |           | 
      st    p          h0         

3. 最后接回

            __________
            |                  |
            |                 V
D->1   2<-3<-4    5->NULL             
       |________|                




 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
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(m<1 || m>=n || !head) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        
        // move head to (m-1)th node
        for(int i=0; i<m-1; i++)
            head = head->next;
        
        // reverse list from pre with length n-m+1    
        ListNode *pre = head->next, *cur = pre->next;
        for(int i=0; i<n-m; i++) {
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        
        head->next->next = cur;
        head->next = pre;
        head = dummy->next;
        delete dummy;
        return head;
    }
};

No comments:

Post a Comment