62. 鏈表重排[Reorder List]

【本文鏈接】

http://www.cnblogs.com/hellogiser/p/reorder-list.html

【題目】

Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,

Given {1,2,3,4,5,6,7}, reorder it to {1,7,2,6,3,5,4}.

【分析】

題目思路比較直接：

(1)找到鏈表的中間節點，把鏈表劃分成2個子鏈表；如果原鏈表長度為奇數，那麼第一個子鏈表的長度多1；

(2)翻轉第二個子鏈表；

(3)交叉合並兩個子鏈表。

例如{1,2,3,4,5,6,7}

(1)找到鏈表的中間節點為4，把鏈表劃分成2個子鏈表：{1,2,3,4}和{5,6,7}；

(2)翻轉第二個子鏈表得到{7,6,5}

(3)交叉合並{1,2,3,4}和{7,6,5}得到{1,7,2,6,3,5,4}

【代碼】

 C++ Code  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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93   // 62_ReorderList.cpp : Defines the entry point for the console application.
//
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/5/30
*/
#include "stdafx.h"

struct ListNode
{
    int value;
    ListNode *next;
};

// find middle node of list
ListNode *FindMiddleNode(ListNode *head)
{
    if(NULL == head)
        return NULL;
    ListNode *fast = head, *slow = head;
    while(fast != NULL && fast->next != NULL)
    {
        // move fast 2 steps
        fast = fast->next->next;
        if (fast == NULL)
            break;
        // move slow 1 step
        slow = slow->next;
    }
    return slow;
}

// reverse list
ListNode *ReverseList(ListNode *head)
{
    if(NULL == head || NULL == head->next)
        return head;
    ListNode *prev = NULL, *cur = head, *next = NULL;
    while(cur != NULL)
    {
        // save next
        next = cur->next;
        // reverse
        cur->next = prev;
        // update prev and cur
        prev = cur;
        cur = next;
    }
    return prev;
}

// cross merge list
ListNode *CrossMergeList(ListNode *head1, ListNode *head2)
{
    if(NULL == head1)
        return head2;
    else if (NULL == head2)
        return head1;

    ListNode *node1 = head1, *node2 = head2;
    while(node2 != NULL)
    {
        ListNode *temp1 = node1->next;
        ListNode *temp2 = node2->next;
        node1->next = node2;
        node2->next = temp1;
        // update node1 node2
        node1 = temp1;
        node2 = temp2;
    }
    return head1;
}

// reorder list
ListNode *ReOrderList(ListNode *head)
{
    if(NULL == head || NULL == head->next)
        return head;

    // find middle node of list
    ListNode *middle = FindMiddleNode(head);
    // split into 2 lists
    ListNode *head1 = head;
    ListNode *head2 = middle->next;
    // detach the 2 lists
    middle->next = NULL;
    // reverse list2
    head2 = ReverseList(head2);
    // cross merge 2 lists
    return CrossMergeList(head1, head2);
}

【參考】

http://blog.csdn.net/whuwangyi/article/details/14146461

【本文鏈接】

http://www.cnblogs.com/hellogiser/p/reorder-list.html