-
Notifications
You must be signed in to change notification settings - Fork 0
/
reorder_list.py
90 lines (71 loc) · 2.81 KB
/
reorder_list.py
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
'''
Question: https://leetcode.com/problems/reorder-list/
'''
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
'''
Part 1:
Find the middle of the linked list using two pointers
`slow` and `fast`
Part 2:
Reverse the second half using `reverse linked list` logic
Part 3:
Merge the first half and second half (reversed) together,
joining nodes alternately
TC: O(n)
SC: O(1)
'''
### Consider Eg: 1->2->3->4->5->None
## Part 1:
# init two pointers `slow` and `fast`
slow, fast = head, head.next
# while the `fast` pointer doesn't reach the end of the LL
while fast and fast.next:
# move `slow` pointer to the next node
slow = slow.next
# move `fast` pointer two nodes ahead
fast = fast.next.next
# After Part 1
# Eg: 1 -> 2 -> 3 -> 4 -> 5 -> None
# slow fast
# `slow` pointer is at the center of the LL
# so init `second` as the head of the second half of LL
second = slow.next
# since we have divided the list into two halves, end the first half with None
slow.next = None
# init `prev` as None (required for reversing the second half)
prev = None
# Eg: 1 -> 2 -> 3 -> None 4 -> 5 -> None
# slow.next second
# while `second` does not reach the end i.e. None
while second:
# store the next node of `second` in tmp since we will be breaking
# this link
tmp = second.next
# reverse the link by assigning `second` node to `prev`
second.next = prev
# now move the `prev` pointer to `second`
prev = second
# and `second` pointer to its original next i.e `tmp`
second = tmp
first, second = head, prev
# After Part 2
# 1 -> 2 -> 3 -> None None <- 4 <- 5
# first second
# since second half will always be shorter than first half
while second:
# assign actual nexts of `first` and `second` in temp vars
# since we will break these links
tmp1, tmp2 = first.next, second.next
# connect first node to the last node
first.next = second
# connect last node to first's next node
second.next = tmp1
# move `first` and `second` to thier original nexts
first, second = tmp1, tmp2