Leetcode # 143. Reorder List

https://leetcode.com/problems/reorder-list/

Key point

使用一快一慢的pointer來找到length和middle node

Solution

class Solution:
  def reorderList(self, head: Optional[ListNode]) -> None:
    """
    Do not return anything, modify head in-place instead.
    """
    # Find length and middle node
    n = 0
    cur = head
    half = head
    while cur:
      n += 1
      if n % 2 == 0:
        half = half.next
      cur = cur.next

    # Reverse the second half part of the list
    pre, cur = None, half
    while cur:
      cur_next = cur.next
      cur.next = pre
      pre = cur
      cur = cur_next

    # Merge the first half part and the second half part
    cur = [head, pre]
    for i in range(n - 1):
      cur_next = cur[i % 2].next
      cur[i % 2].next = cur[(i + 1) % 2]
      cur[i % 2] = cur_next

Last Updated on 2023/08/16 by A1go