Thursday, November 20, 2014

[LeetCode] Reorder List

Given a singly linked list LL0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}

思路:

很经典的题,考到了链表的很多特性和技巧,要迅速写对写好不容易。大致思路分三步:
(1) 找到链表后一半。
(2) 将后一半节点反转。
(3) 将后一半节点依次插入前一半。

解法实现时有不少要注意的地方:

I. 奇偶链表长度:

偶数长度:1->2->3->4
(1) 1->2->3<-4
      |                |
      h1             h2

(2) 1->4->2->3
                 |     |
                 h1  h2 

奇数长度:1->2->3->4->5
(1) 1->2->3<-4<-5
      |                      |
      h1                   h2

(2) 1->5->2->3<-4
                 |           |
                 h1        h2

(3) 1->5->2->4->3
                             |
                            h1, h2

规律:如果链表长度为L,无论L是奇数还是偶数,都从第k = L/2+1 个节点起反转。

II  如何找到第k=L/2+1个节点?

可以扫描两遍,第一遍得到L,并计算k。而第二遍扫描找到节点k。而更好的方法则是采用快慢双指针的策略:f每次走两步,s每次走一步。当f到达最后一个节点(而不是NULL)时,s指向k。同样分奇偶长度来验证:

偶数长度:1->2->3->4
(1) 1->2->3->4->NULL
            |     |
            s    f

(2) 1->2->3->4->NULL
                  |     |
                  s    f

奇数长度:1->2->3->4->5
(1) 1->2->3->4->5->NULL
            |     |
            s    f

(2) 1->2->3->4->5->NULL
                  |          |
                  s         f

III 如何将后一半反转的链表节点依次插入前一半中?

(1) 用双指针left/right分别从左右两头开始向中间扫描。依次将right所指节点插入left节点后面。每次插入后,left需要移动两次。

(2) 终止条件:当right扫描到最后一个节点(left->next==NULL)时结束,而该节点就是原链表中的第k=L/2+1个节点。

由于步骤比较复杂,写的时候尽量分成子程序写。
         


 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
class Solution {
public:
    void reorderList(ListNode *head) {
        ListNode *mid = findMid(head);
        ListNode *right = reverseList(mid);
        ListNode *left = head;
        
        while(right && right->next) {
            ListNode *target = right;
            right = right->next;
            target->next = left->next;
            left->next = target;
            left = left->next->next;
        }
    }
    
    ListNode *findMid(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next) {
            fast = fast->next;
            if(fast->next) fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
    
    ListNode *reverseList(ListNode *head) {
        if(!head) return head;
        ListNode *pre = head, *cur = head->next;
        while(cur) {
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        head->next = NULL;
        return pre;
    }
};

No comments:

Post a Comment