Scale Engineer

Reorder List

Med
#0143Time: O(N)Space: O(N)5 companies
Patterns
RecursionTwo Pointers
Data structures
Linked ListStack
Companies
Goldman SachsLinkedInTikTokYahoo

Prompt

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 * 104].
  • 1 <= Node.val <= 1000

Approaches

3 approaches with complexity analysis and trade-offs.

This approach simplifies the problem by converting the linked list into a more flexible data structure like an ArrayList. By storing all nodes in a list, we can easily access any node by its index. This allows us to use two pointers, one at the beginning and one at the end, to rebuild the linked list in the desired order.

Algorithm

  • Create an ArrayList to store the nodes of the linked list.
  • Traverse the linked list from the head and add each node to the ArrayList.
  • Initialize two pointers, left = 0 and right = list.size() - 1.
  • Iterate while left < right:
    • Set the next of the node at index left to point to the node at index right.
    • Increment left.
    • If left becomes equal to right, break the loop (for odd length lists).
    • Set the next of the node at index right to point to the node at the new index left.
    • Decrement right.
  • Set the next pointer of the last node in the reordered sequence (at index left) to null.

Walkthrough

First, we iterate through the original linked list from head to tail. During this traversal, we add each node to an ArrayList. After the list is fully stored, we can re-wire the next pointers. We use two integer indices, left starting at 0 and right starting at size - 1. We iterate as long as left < right. In each step, we link the node at left to the node at right (nodes.get(left).next = nodes.get(right)). Then, we increment left. To continue the chain, we link the node at right to the new left node (nodes.get(right).next = nodes.get(left)). Then we decrement right. This process continues until the pointers meet or cross. Finally, the next pointer of the last node in the new sequence (which will be at index left when the loop terminates) must be set to null to signify the end of the list.

import java.util.ArrayList;import java.util.List; /** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public void reorderList(ListNode head) {        if (head == null || head.next == null) {            return;        }         // 1. Store all nodes in a list        List<ListNode> nodes = new ArrayList<>();        ListNode current = head;        while (current != null) {            nodes.add(current);            current = current.next;        }         // 2. Re-wire the nodes using two pointers        int left = 0, right = nodes.size() - 1;        while (left < right) {            nodes.get(left).next = nodes.get(right);            left++;            if (left == right) {                break;            }            nodes.get(right).next = nodes.get(left);            right--;        }                // 3. Set the last node's next to null        nodes.get(left).next = null;    }}

Complexity

Time

O(N)

Space

O(N)

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Avoids complex pointer manipulation during traversal.

Cons

  • Requires extra space proportional to the number of nodes, which can be significant for large lists.

  • Generally not the expected solution in an interview setting where in-place solutions are preferred.

Solutions

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public void ReorderList ( ListNode head ) { ListNode slow = head ; ListNode fast = head ; while ( fast . next != null && fast . next . next != null ) { slow = slow . next ; fast = fast . next . next ; } ListNode cur = slow . next ; slow . next = null ; ListNode pre = null ; while ( cur != null ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } cur = head ; while ( pre != null ) { ListNode t = pre . next ; pre . next = cur . next ; cur . next = pre ; cur = pre . next ; pre = t ; } } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem