Reorder List
题目
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}, reorder it to {1,4,2,3}.
思路
将链表从中间断开，分为前链表和后链表，后链表反转，再将两链表合并。
解题
c++ 版
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
|
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if(!head || !head->next)
return ;
ListNode *slow=head,*fast=head,*prev=NULL;
while(fast && fast->next){
prev=slow;
slow=slow->next;
fast=fast->next->next;
}
prev->next=NULL;
slow=reverse(slow);
ListNode *cur=head,*tmp;
while(cur->next){
tmp=cur->next;
cur->next=slow;
slow=slow->next;
cur->next->next=tmp;
cur=tmp;
}
cur->next=slow;
}
ListNode* reverse(ListNode *head){
if(!head || !head->next)
return head;
ListNode dummy(-1);
dummy.next=head;
ListNode *pre=head,*cur=head->next;
while(cur){
pre->next=cur->next;
cur->next=dummy.next;
dummy.next=cur;
cur=pre->next;
}
return dummy.next;
}
};
|
python 版
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
|
class Solution:
def reorderList(self, head):
if not head or not head.next:
return
slow=head
fast=head
prev=None
while fast and fast.next:
prev=slow
slow=slow.next
fast=fast.next.next
prev.next=None
slow=self.reverse(slow)
cur=head
while cur.next:
tmp=cur.next
cur.next=slow
slow=slow.next
cur.next.next=tmp
cur=tmp
cur.next=slow
def reverse(self,head):
if not head or not head.next:
return head
dummy=ListNode(-1)
dummy.next=head
prev=dummy.next
cur=prev.next
while cur:
prev.next=cur.next
cur.next=dummy.next
dummy.next=cur
cur=prev.next
return dummy.next
|
