【本文链接】
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.****.net/whuwangyi/article/details/14146461
【本文链接】
http://www.cnblogs.com/hellogiser/p/reorder-list.html
