Split Linked List Alternatingly

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Split linked list into two halves alternately (first, third, fifth...

Intuition

Split linked list into two halves alternately (first, third, fifth... and second, fourth, sixth...).

Algorithm

1Two pointers: odd and even. Advance both skipping one node each. Split: odd.next = null.

Common Pitfalls

• Same as LC 328 (odd-even list). O(n) O(1). Maintain two separate chains and separate them.

Split Linked List Alternatingly.java

Java

// Approach: Two-pointer: one for even-indexed nodes (second list) and one for odd-indexed; split into two.
// Time: O(n) Space: O(1)
class Solution {
    // Function to append a new node with newData at the end of a linked list
    Node[] alternatingSplitList(Node head) {
        Node first = new Node(0), second = new Node(0);
        Node dummyFirst = first, dummySecond = second;
        int i = 1;
        while (head != null) {
            if (i % 2 == 0) {
                dummySecond.next = head;
                dummySecond = dummySecond.next;
            } else {
                dummyFirst.next = head;
                dummyFirst = dummyFirst.next;
            }
            head = head.next;
            i++;
        }
        dummyFirst.next = null;
        dummySecond.next = null;
        return new Node[] { first.next, second.next };
    }
}

Was this solution helpful?