Reverse LinkedList

链表翻转

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. 将第二个链表的元素间隔地插入第一个链表中。
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
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

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)

# while reversed_list_head:
# print(reversed_list_head.val)
# reversed_list_head = reversed_list_head.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
Donate article here
Share the post