Reorder List
Given a singly linked list L: L0->L1->...->Ln-1->Ln, reorder it to: L0->Ln->L1->Ln-1->L2->Ln-2->... Tags: Linked List
Try It!
Discussion
Video
Solution
# 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: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head:
return
fast = head.next
slow = head
# ensure the first part has the same or one more node
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# reverse the second half
cur = slow.next
slow.next = None
prev = None
while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
# combine first part and second part
first = head
second = prev
while second:
tmp = second.next
second.next = first.next
first.next = second
first = first.next.next
second = tmp