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}.
解题思路
- 使用两个指针slow和fast，slow移动一次，fast移动两次，直到fast为最后一个元素
- 在slow的地方将链表断开，将slow之后的list翻转
- 将head和slow进行一一merge合并
Go实现
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
|
func (head *ListNode) {
if head == nil || head.Next == nil{
return
}
slow := head
fast := head
var prev *ListNode
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
prev = slow
slow = slow.Next
}
prev.Next = nil
current1 := head
current2 := reverseList(slow)
for current1.Next != nil && current2.Next != nil{
next1 := current1.Next
current1.Next = current2
next2 := current2.Next
current2.Next = next1
current1 = next1
current2 = next2
}
current1.Next = current2
}
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil{
return head
}
newHead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
|
Runtime: 25 ms 50.00%
近期评论