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...

See our study guide for structured GFG and LeetCode practice.

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?