Day 22– Reorder List | Blind75 | Java

Today’s problem is LeetCode 143 — Reorder List.

The goal is to reorder the linked list from:

L0 → L1 → L2 → ... → Ln

to:

L0 → Ln → L1 → Ln-1 → L2 → ...

Approach 1: Brute Force — Using Extra Space

Idea

Store all linked-list nodes in an ArrayList. Then use two pointers, one from the beginning and one from the end, to connect the nodes alternately.

Java Code

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        List<ListNode> nodes = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            nodes.add(curr);
            curr = curr.next;
        }
        int left = 0;
        int 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--;
        }
      nodes.get(left).next = null;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

Approach 2: Optimal — Three-Step Linked List Approach

Idea