reorder-list.py (1616B)
1 # Definition for singly-linked list. 2 # class ListNode: 3 # def __init__(self, val=0, next=None): 4 # self.val = val 5 # self.next = next 6 7 # Do not return anything, modify head in-place instead. 8 9 # IDEA: 10 # first -> last, second -> second to last, inner most is at the end 11 12 # IDEA 2: 13 14 # Cut list in half O(n) time O(1) 15 # interlace lists O(n) 16 # return nothing 17 18 19 class Solution: 20 def reorderList(self, head: Optional[ListNode]) -> None: 21 22 # count length 23 24 current = head 25 n = 0 26 27 while current is not None: 28 n += 1 29 current = current.next 30 31 if n == 1: 32 return None 33 34 # compute half 35 36 midpoint_index = n // 2 37 38 # split half 39 40 midpoint = head 41 42 for i in range(0, midpoint_index - 1): 43 midpoint = midpoint.next 44 45 midpoint_left = midpoint 46 midpoint = midpoint.next 47 midpoint_left.next = None 48 49 # reverse second half 50 51 iterations = n - midpoint_index 52 left = midpoint 53 right = midpoint.next 54 left.next = None 55 56 for i in range(0, iterations - 1): 57 temp_next = right.next 58 right.next = left 59 left = right 60 right = temp_next 61 62 head_of_reverse = left 63 64 # interlace 65 66 # current_left = head 67 # current_right = head_of_reverse 68 69 current = head 70 next_node = head_of_reverse 71 72 while next_node is not None: 73 temp_next = current.next 74 current.next = next_node 75 76 current = next_node 77 next_node = temp_next