Problem

Given a singly linked list, split it into two linked lists. These linked lists will contain the alternate nodes from the given linked list.

Examples

Example 1:

1
2

head = [1,2,3,4,5]
Output: [[1, 3, 5], [2, 4]]

Solution

Method 1 - Iterative

To solve the problem of splitting a singly linked list into two linked lists containing alternate nodes, you can use the following approach in Java:

  1. Initiate 2 head pointers - head1 and head2 and 2 iterating pointers - curr1 and curr2.
  2. Now traverse the original list adding the nodes to lists in an alternating way.
  3. Ensure that after the loop, both curr1.next and curr2.next point to null to terminate the lists correctly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {

	public ListNode[] splitAlternatingNodes(ListNode head) {
		// Edge case: If the head is null or there's only one node, handle accordingly
		if (head == null || head.next == null) {
			return new ListNode[] {
				head, null
			};
		}

		// Pointers for the two new linked lists
		ListNode head1 = head;
		ListNode head2 = head.next;

		ListNode curr1 = head1;
		ListNode curr2 = head2;

		ListNode curr = head.next.next;

		boolean addToFirst = true; // To alternate between the two lists
		while (curr != null) {
			if (addToFirst) {
				curr1.next = curr;
				curr1 = curr1.next;
			} else {
				curr2.next = curr;
				curr2 = curr2.next;
			}

			curr = curr.next;
			addToFirst = !addToFirst; // Switch the boolean
		}

		// Ensure the last nodes point to null
		curr1.next = null;
		curr2.next = null;

		return new ListNode[] {
			head1, head2
		};
	}
}