Reorder List
Problem
https://leetcode.com/problems/reorder-list/
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
The number of nodes in the list is in the range
[1, 5 * 10:sup:`4`].1 <= Node.val <= 1000
Pattern
Linked List, Two Pointers, Stack, Recursion
Approaches
Code
from __future__ import annotations
class ListNode:
"""Node in a linked list."""
def __init__(self, val: int = 0, next: ListNode | None = None):
self.val = val
self.next = next
@classmethod
def from_list(cls, vals: list[int]) -> ListNode | None:
dummy = cls(0)
node = dummy
for val in vals:
node.next = cls(val)
node = node.next
return dummy.next
def to_list(self) -> list:
result = []
node = self
while node:
result.append(node.val)
node = node.next
return result
def reorderList(head: ListNode | None) -> None:
"""
Do not return anything, modify head in-place instead.
"""
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev = None
while slow:
original_next = slow.next
slow.next = prev
prev = slow
slow = original_next
while head and prev:
original_head_next = head.next
original_prev_next = prev.next
head.next = prev
prev.next = original_head_next
head = original_head_next
prev = original_prev_next
Test
>>> from reorder_list__split_and_merge import reorderList, ListNode
>>> head = ListNode.from_list([1, 2, 3, 4])
>>> reorderList(head)
>>> head.to_list()
[1, 4, 2, 3]
>>> head = ListNode.from_list([1, 2, 3, 4, 5])
>>> reorderList(head)
>>> head.to_list()
[1, 5, 2, 4, 3]
Code
from __future__ import annotations
class ListNode:
"""Node in a linked list."""
def __init__(self, val: int = 0, next: ListNode | None = None):
self.val = val
self.next = next
@classmethod
def from_list(cls, vals: list[int]) -> ListNode | None:
dummy = cls(0)
node = dummy
for val in vals:
node.next = cls(val)
node = node.next
return dummy.next
def to_list(self) -> list:
result = []
node = self
while node:
result.append(node.val)
node = node.next
return result
def reorderList(head: ListNode | None) -> None:
"""Reorder ``head`` in-place by interleaving front and back."""
nodes = []
node = head
while node:
nodes.append(node)
node = node.next
i = 0
j = len(nodes) - 1
while i < j:
nodes[i].next = nodes[j]
i += 1
if i >= j:
break
nodes[j].next = nodes[i]
j -= 1
nodes[i].next = None
Test
>>> from reorder_list__brute_force import reorderList, ListNode
>>> head = ListNode.from_list([1, 2, 3, 4])
>>> reorderList(head)
>>> head.to_list()
[1, 4, 2, 3]
>>> head = ListNode.from_list([1, 2, 3, 4, 5])
>>> reorderList(head)
>>> head.to_list()
[1, 5, 2, 4, 3]