leetcode 143. Reorder List


  1. Reorder List:题目链接
原理

AC 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
struct ListNode*  reverse(struct ListNode* head){
struct ListNode* pre = NULL;
struct ListNode* cur = head;
struct ListNode* next = NULL;
while (cur != NULL){
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}

void reorderList(struct ListNode* head){
if (head == NULL || head->next == NULL){
return;
}
struct ListNode* dummyHead = (struct ListNode*) malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast->next != NULL && fast->next->next!= NULL) {
slow = slow->next; // 一次移动一个
fast = fast->next->next; // 一次移动2个
}


struct ListNode* p = slow;
// p指向链表中间节点 从链表头到p形成一个链表dummyHead 从p的后一个节点到尾节点形成一个链表q
// 逆转中间往后部分的链表 q = reverse(p->next)
struct ListNode* q = p->next;
if (q == NULL) {
return head;
}
q = reverse(q); //逆转之后新的链表
p->next = NULL; //置空

// 合并dummyHead 、q两个链表乘一个新的链表
p = dummyHead->next;
struct ListNode* tail = dummyHead;
int flag = 0;
while (p != NULL && q != NULL) {
if (flag == 0) {
tail->next = p;
tail = p;
p = p->next;
flag = 1;
}else{
tail->next = q;
tail = q;
q = q->next;
flag = 0;
}
}

if (p != NULL) {
tail->next = p;
}

if (q != NULL) {
tail->next = q;
}
return dummyHead->next;
}

/*
Runtime: 16 ms, faster than 92.53% of C online submissions for Reorder List.
*/

文章目录
|