又是一道单链表相关的题目。
一开始没有思路，借鉴了高手们的博客，于是采用：
1.先找链的近似中间点，从中间点把链切为两段；
2.翻转后半段的链；
3.将后半段链按题目要求插入前半段链；
需要注意的是指针的非空检查。
特别强调，如果调用p->next或对其赋值，一定要保证p!=NULL.
还有一些关键语句的次序一定不要搞错，之前多次出现程序写好后修改时，将break语句或者p->next=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
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 |
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class
Solution { //翻转链表，假设链表没有头结点 ListNode* reverse(ListNode* head) { if
(head==NULL || head->next==NULL) return
head; ListNode* p = head; ListNode* p_pre = NULL; ListNode* p_next = p->next; while
(p != NULL) { p_next = p->next; p->next = p_pre; p_pre = p; p = p_next; } return
p_pre; //返回尾结点 } //交叉插入函数 ListNode* crossInsert(ListNode* h1, ListNode* h2) { ListNode* p1 = h1; ListNode* p1_next = NULL; ListNode* p2 = h2; ListNode* p2_next = NULL; while
(p1 != NULL && p2!=NULL) { //必须要加入p2!=NULL的判断，因此出错!! p1_next = p1->next; p2_next = p2->next; p1->next = p2; p2->next = p1_next; p1 = p1_next; p2 = p2_next; } return
h1; }public: void
reorderList(ListNode *head) { if
(head==NULL || head->next==NULL) return; ListNode* dummy = new
ListNode(0); dummy->next = head; ListNode* p1 = dummy; ListNode* p2 = dummy; //按照两步一步法，求近似中间点的位置，中间点位置偏前 //前半段从dummy->next开始到p1结束，后半段从p1->next开始 while
(p2!=NULL && p2->next!=NULL) { p1 = p1->next; p2=p2->next->next; } p2 = p1->next; p1->next = NULL; //将链打开，按此方法分割，前段链长度>=后段链长度，该句的位置放错导致出错!! ListNode* h1 = dummy->next; ListNode* h2 = reverse(p2); crossInsert(h1, h2); delete
dummy; }}; |
LeetCode: Reorder List,布布扣,bubuko.com
原文：http://www.cnblogs.com/zanghu/p/3619263.html