Problem

Given a linked list with head pointer and a number n. Split the linked list into two halves such that first half contains 1/n elements and remaining linkedlist contains remaining elements. Return the head of the second list or the right partition pointer.

Examples

Example 1:

Input: head = [1, 2, 3, 4, 5, 6, 7, 8], n = 2
Output: [5, 6, 7, 8]
Explanation: As n = 2, we have 2 lists like this[[1, 2, 3, 4], [5, 6, 7, 8]] and we return the list with head at 5.

Example 2:

Input: head = [1, 2, 3, 4, 5, 6, 7, 8], n = 4
Output: [3, 4, 5, 6, 7, 8]
Explanation: As n = 4, we have 2 lists:[[1, 2], [3, 4, 5, 6, 7, 8]] and we return the second list's head pointer i.e. 3.

Solution

First, observe the pattern: for n=2, the list is divided into two equal halves. For n=4, the left partition has 2 elements and the right has 6 elements, meaning the list is split at 1/4th of its length. The general pattern is that for a given n, the list is partitioned at the size/n-th element.

Method 1 - Calculate the length of list and split

A straightforward solution would be to calculate the size of the list and then traverse to the size/n-th element, where the list is partitioned. However, there is a potential issue if the list is circular. We need to detect circularity, and if the list is circular, we cannot partition it and should return an error.

We can detect the loop as discussed here - Detect a loop or cycle in the Linked List.

Code

Java
public ListNode splitLinkedListNode(ListNode head, int n) {
	//O(size)
	if (hasLoop(head)) {
		return null;
	}
	//O(size)
	int size = size(head);

	if (n >= size || size == 0) {
		return null;
	}

	int split = 0;

	if (size % n == 0) {
		split = size / n;
	} else {
		split = (size - 1) / n;
	}

	//O(n)
	ListNode temp = head;
	ListNode last = head;

	while (split >= 0) {
		last = temp;
		temp = temp.next;
		split--;
	}

	last.next = null;

	return temp;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 - Slow and Fast Pointer approach

Can we achieve this in a cleaner way? By examining the cycle detection code, we can use a similar technique to split the list. Observe that n acts as the speed factor for the fast pointer, meaning the fast pointer moves n times faster than the slow pointer. For example, if the slow pointer moves 4 steps while n=2, the fast pointer moves 2*4=8 steps.

This means we can split the list using the slow and fast pointers as follows:

 1. Use two pointers: slow and fast, where fast moves `n` times faster than slow.
 2. At each step, the slow pointer moves one step while the fast pointer moves `n` steps, continuing until the fast pointer reaches the end of the list.
 3. If the fast pointer reaches the end, the slow pointer effectively points to the head of the right partition.
 4. If a cycle is detected by the slow and fast pointers meeting, exit with an error indicating the list is circular.

Code

Java
public ListNode splitLinkedListNode(ListNode head, int n) {
	ListNode slow = head;
	ListNode fast = head;
	ListNode prev = head;

	while (fast != null && slow != null) {
		int count = 0;
		prev = slow;
		slow = slow.next;

		while (count < n && fast != null) {
			fast = fast.next;
			count++;
		}

		if (slow == fast) {
			return null;
		}
	}

	if (prev != null) {
		prev.next = null;
	}

	return slow;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)