Split The Linked List

Given a linked list and a number n. Split the link list into two based on the following pattern

input: 1->2->3->4->5->6->7->8->null and n=2
output: 1-2->3->4->null and 5->6->7->8->null

input: 2->3->1->4->6->7->7->6->null and n=4
output: 2-3->null and 1->4->6->7->7->6->null

return the right partition pointer.

First note that pattern. For n=2 it is effectively partitioning the list into two halves. But for n = 4 w can see left partition has 2 element and right has 6 element. So, basically list is partitions at 1/4th of its length. So what’s the pattern here? For a given n list is partitioned into two halves at size/k th element.

So, a quick dirty solution would be to calculate size of the list and traverse the linked list upto size/k th element. Then we partition the link list at size/kth element. There is one challenge we need to consider. What will happen if the list is circular? So, we need to detect if the list is circular. In that case we can’t partition the list and return as error.

Detecting Cycle
I have discussed this in a separate post here. However, the bottom line is to use two pointers , one slow and another fast (double speed of slower). Then traverse the list until we reach end points or if a cycle is there then we never reach end point. But as fast pointer is moving in double speed then it will ultimately meet the slow speed pointer and at that point we know that we have a cycle.

Below is the simple counting based solution which runs in O(N), where N is the size of the linked list.

public static boolean detectCycle(ListNode head){
    ListNode slow = head;
    ListNode fast = head.next;
    
    while(slow != null && fast != null && slow != fast){
        if(fast.next == null){
             break;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if(slow != null && fast != null && slow == fast){
        return true;
    }
    
    return false;
}
public static int size(ListNode head){
    ListNode temp = head;
    int count  = 0;
    
    while(temp != null){            
        count++;
        temp = temp.next;
    }
    
    return count;
}   

public static ListNode splitLinkedListNode(ListNode head, int n){
	//O(size)
    if(detectCycle(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;
}

Cleaner Solution
Can we do it more cleaner way? If we look into the cycle detection code then we should figure out that we can use the same technique to split the list. We can notice that input n is the speed factor of the faster pointer i.e. fast pointer is n times fast than slow pointer. That is if slow goes 4 steps with n=2 then fast goes 2*4 = 8 steps. That means we can split the array using slow and fast pointer as follows –

1. Keep two pointers - slow and fast where fast moves n times faster than slow.
2. At each step slow will move one step but fast will move n step until the faster reaches the end of the list.
3. If fast pointer reaches end of the list then slow pointer is effectively pointing to the head of right partition. 
4. If we never reach end point due to a cycle then we can detect the cycle by checking if slow and fast pointer met In that case we exit with error.

Below is the solution which also runs in O(N).

public static ListNode splitLinkedListNode2(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;
}