LeetCode 143. Reorder List

Blind 75 — Programming & Technical Interview Questions — Explanation Series

The Problem:

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]

The Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

The Explanation:

The big thing to notice when reading this problem is that you cannot change the values of the nodes you must changes the order of the nodes themselves. This makes it harder but if you think about how to solve it without this constraint and parlay that into solving with it you can solve this problem easily. When changing values you would just go through the list, keep track of the values, then go through it again updating the values accordingly. So what if instead of storing values you stored the nodes themselves in a list? This allows you to then work from the outside in updating the order of the list. After you store all the nodes in a list keep a left and right pointer and work inwards until the left is equal to the right. There are a few corner cases that will be covered in the code.

The Python Programming Solution:

First we pass through the list once storing all the nodes. Then we work from the outside in starting with updating the left nodes next pointer to the right node. After that we increase the left pointer and if it is ≥ to the right pointer we know that right node is the new tail so we break. If it isn’t we update the right node, which is now the previous left nodes next, to the current left node and decrease the right pointer. Once the while loop is complete we make sure to set the tails next pointer to none so no cycle appears and return the original head.

# 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:
    """
    Do not return anything, modify head in-place instead.
    """

    nodes = []

    curr = head
    while curr:
      nodes.append(curr)
      curr = curr.next
    
    l, r = 0, len(nodes) - 1

    while l < r:
      nodes[l].next = nodes[r]
      l += 1
      if l >= r: 
        break
      nodes[r].next = nodes[l]
      r -= 1
    
    nodes[l].next = None
    
    return head

Information:

Medium: medium.com/@nkwade
Website: nkwade.dev
LinkedIn: linkedin.com/in/nkwade
GitHub: github.com/nkwade
Email: nicholas@nkwade.dev
Twitter: twitter.com/nkwade_world