Skip to content

Weaving the Playlist

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 11 Session 2 (Click for link to problem statements)

Weaving the Playlist

A playlist is a linked list L0 -> L1 -> ... -> Ln. To keep listeners engaged, you reweave it into L0 -> Ln -> L1 -> Ln-1 -> ..., reordering the existing nodes in place.

Modify the list in place; do not create new nodes.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorder_list(head):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-30 mins
  • 🛠️ Topics: Linked Lists, Fast & Slow Pointers, In-Place Reversal, Merging Two Lists

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: What does the reordered list look like?

    • A: It alternates between the front and the back of the original list: first node, then last node, then second node, then second-to-last node, and so on until every node is used.

  • Q: Can we create new nodes or copy values into a new list?

    • A: No. The problem requires modifying the list in place by rewiring the next pointers of the existing nodes.

  • Q: Does the function return anything?

    • A: No. It reorders the list in place, so the caller still traverses from the original head.
HAPPY CASE
Input: head = 1 -> 2 -> 3 -> 4 -> 5
Output: 1 5 2 4 3
Explanation: L0=1 is followed by Ln=5, then L1=2 is followed by Ln-1=4, and the middle node 3 ends the list.

Input: head = 1 -> 2 -> 3 -> 4
Output: 1 4 2 3
Explanation: With an even length, the front and back alternate perfectly: 1, then 4, then 2, then 3.

EDGE CASE
Input: head = 7
Output: 7
Explanation: A single node has nothing to weave; the list is unchanged.

Input: head = 1 -> 2
Output: 1 2
Explanation: L0 followed by Ln is already the original order, so the list is unchanged.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List Rearrangement Problems, we can consider the following approaches:

  • Fast & Slow Pointers: Find the middle of the list in one pass so we can split it into two halves.
  • In-Place Reversal: Reverse the second half so its nodes can be consumed back-to-front without extra memory.
  • Merging Two Lists: Weave the first half and the reversed second half together by alternating nodes.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
The reordered list alternates between the front of the list and the back of the list. Split the list at its midpoint, reverse the second half so the last node comes first, and then merge the two halves by alternating one node from each. All three steps only rewire next pointers, so no new nodes are created.

1) If the list has fewer than 3 nodes, it is already reordered; return.
2) Find the middle of the list using a slow pointer and a fast pointer.
   a) Advance `slow` by one and `fast` by two until `fast` reaches the end.
   b) `slow` now sits at the end of the first half.
3) Split the list: the second half starts at `slow.next`, and set `slow.next = None`.
4) Reverse the second half by redirecting each node's `next` pointer to the node before it.
5) Merge the two halves, alternating nodes:
   a) Save `first.next` and `second.next`.
   b) Point `first.next` to `second`, and `second.next` to the saved node from the first half.
   c) Advance both pointers and repeat until the reversed half is exhausted.

⚠️ Common Mistakes

  • Forgetting to cut the first half off from the second half (slow.next = None), which leaves a cycle in the list.
  • Losing the rest of a half during the merge by overwriting a next pointer before saving it.
  • Building a brand-new list of nodes or an array of values instead of rewiring the existing nodes in place.
  • Off-by-one errors in the fast/slow loop that split an odd-length list in the wrong spot.

4: I-mplement

Implement the code to solve the algorithm.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorder_list(head):
    if not head or not head.next:
        return

    # 1) Find the middle of the list (slow ends the first half)
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # 2) Detach and reverse the second half
    second = slow.next
    slow.next = None
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt

    # 3) Weave the two halves together, alternating nodes
    first, second = head, prev
    while second:
        first_next, second_next = first.next, second.next
        first.next = second
        second.next = first_next
        first, second = first_next, second_next

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: head = 1 -> 2 -> 3 -> 4 -> 5

    • Find middle: slow stops at node 3, fast at node 5, so the first half is 1 -> 2 -> 3.
    • Split and reverse: the second half 4 -> 5 becomes 5 -> 4.
    • Weave: 1 takes 5 as its next, 2 takes 4 as its next, and 3 remains the tail.
    • Output: 1 5 2 4 3

  • Input: head = 1 -> 2 -> 3 -> 4

    • Find middle: slow stops at node 2, so the first half is 1 -> 2.
    • Split and reverse: the second half 3 -> 4 becomes 4 -> 3.
    • Weave: 1 takes 4 as its next, 2 takes 3 as its next.
    • Output: 1 4 2 3

  • Input: head = 7

    • The early return fires because the list has fewer than two nodes.
    • Output: 7

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of nodes in the linked list.

  • Time Complexity: O(N) because finding the middle, reversing the second half, and weaving the halves each traverse the list once.
  • Space Complexity: O(1) because every step rewires existing pointers iteratively; no extra data structures or recursion are used.

Clone this wiki locally