链表翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def reverse(head):
if not head:
return head
dummy = ListNode(0)
dummy.next = head
tail = dummy
while head.next:
tmp = head.next
head.next = tmp.next
tmp.next = tail.next
tail.next = tmp
return dummy.next
|
Leetcode No.143
Given a singly linked list L: L0->L1->...->Ln-1->Ln, reorder it to: L0->Ln->L1->Ln-1->L2->Ln-2->...
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
思路
- 使用快慢指针来找到链表的中点，并将链表从中点处断开，形成两个独立的链表。
- 将第二个链翻转。
- 将第二个链表的元素间隔地插入第一个链表中。
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
|
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head:
return head
def reverse(head):
if not head:
return head
dummy = ListNode(0)
dummy.next = head
tail = dummy
while head.next:
tmp = head.next
head.next = tmp.next
tmp.next = tail.next
tail.next = tmp
return dummy.next
dummy = ListNode(0)
dummy.next = head
slow = quick = dummy
while quick and quick.next:
quick = quick.next.next
slow = slow.next
reversed_list_head = reverse(slow.next)
slow.next = None
cur_left = dummy.next
while cur_left and reversed_list_head:
tmp_cur = cur_left.next
tmp_reversed_list_head = reversed_list_head.next
cur_left.next = reversed_list_head
reversed_list_head.next = tmp_cur
cur_left = tmp_cur
reversed_list_head = tmp_reversed_list_head
return dummy.next
|