Problem

Given a list, split it into two sublists — one for the front half, and one for the back half. If the number of elements is odd, the extra element should go in the front list.

Examples

Example 1:

1
2

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

Solution

This linked list question is challenging due to the tricky edge cases that need consideration, making it more difficult than it seems to get everything right at once.

Method 1 - Get length of list

A straightforward solution involves iterating through the list twice: first to count the elements (using Find the length of the linked list) and second to find the split point.

Can we improve upon this method? Absolutely.

Method 2 - Using slow and fast pointers

We employ two pointers, lets call them slow and fast. The slow pointer moves one node at a time, while the fast pointer progresses two nodes at a time. This is very similar to Middle of the linked list, but with some changes. As, we need to add the previous node to middle, for splitting up, we can handle it using such cases.

When the fast pointer reaches the end of the list, the slow pointer will be at or near the splitting point. It’s important to handle special cases. The following solution addresses all scenarios effectively. We can either use prev pointer of dummy node.

I prefer the solution with dummy node, where we insert the dummy node at the start. Then, we can point slow to dummy and fast to head. This way we can handle the edge cases.

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

public class Solution {

	public ListNode[] splitLinkedList(ListNode head) {
		if (head == null || head.next == null) {
			return new ListNode[] {
				head, null
			}; // Handle the cases of empty list or single node list
		}

		ListNode slow = dummy;
		ListNode fast = head;
		ListNode prev = null; // To keep track of the node before the slow pointer

		// Use fast and slow pointers to find the middle
		while (fast != null && fast.next != null) {
			prev = slow;
			slow = slow.next;
			fast = fast.next.next;
		}

		// Split the list into two halves
		if (prev != null) {
			prev.next = null; // Break the link to split the list
		}

		return new ListNode[] {
			head, slow
		}; // Return the two halves
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {

	public ListNode[] splitLinkedList(ListNode head) {
		if (head == null || head.next == null) {
			return new ListNode[] {
				head, null
			}; // Handle the cases of empty list or single node list
		}

		ListNode dummy = new ListNode(0, head);
		ListNode slow = dummy;
		ListNode fast = head;

		// Use fast and slow pointers to find the middle
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		ListNode[] ans = new ListNode[]{head, slow.next};
		slow.next = null;

		return ans;
	}
}