Code Destine

Problem Statement

You have given a singly linked list and an integer value X. Partition the given linked list in such a way that all nodes whose value is less than X come before the nodes whose values are greater than or equal to X.

Example 

Input :- head = [5, 4, 10, 15, 1, 7], X = 10
Output :- [5, 4, 1, 7, 10, 15]

Solution

This problem can be solved in the following steps :-

1. Create three variables first, second and temp pointing to the head of the linked list.
2. Move the temp variable by the speed of one node, until it reaches the last node of the linked list.
3. Add the node to the linked list represented by the first variable, if the value of the node is less than X.
4. Add the node to the linked list represented by the second variable, if the value nodes are greater than or equal to X.
5. Assign head of the second linked list to the next of the last node of the first linked list.

Program

public class Main {

	public static void main(String[] args) {
		
		ListNode head = null;		
		ListNode node = new ListNode(5);
		head = node;		
		node.next = new ListNode(4);
		node = node.next;		
		node.next = new ListNode(10);
		node = node.next;		
		node.next = new ListNode(15);
		node = node.next;		
		node.next = new ListNode(1);
		node = node.next;		
		node.next = new ListNode(7);	
		
		Main main = new Main();
		head = main.partition(head, 10);
		while(head != null) {
			System.out.print(head.value + ", ");
			head = head.next;
		}
	}
	
	/* Solution */
	public ListNode partition(ListNode head, int x) {
        
        ListNode firstHead = null;
        ListNode firstTemp = null;
        ListNode secondHead = null;
        ListNode secondTemp = null;
        
        ListNode temp = head;        
        while(temp != null){
            
            if(temp.value < x){                
                if(firstHead == null){
                    firstHead = temp;
                    firstTemp = temp;
                }else {
                    firstTemp.next = temp;
                    firstTemp = temp;
                }                
            }else {
                if(secondHead == null){
                    secondHead = temp;
                    secondTemp = temp;
                }else {
                    secondTemp.next = temp;
                    secondTemp = temp;
                }
            } 
            temp = temp.next;
        }
        if(firstTemp != null){
            firstTemp.next = secondHead;
        }
        if(secondTemp != null){
            secondTemp.next = null;
        }
        
        if(firstHead != null){
            return firstHead;
        }
        return secondHead;        
    }
	
	/* Definition of Linked List Node */
	public static class ListNode {		
		int value;
		ListNode next;
		
		public ListNode(int value) {
			this.value = value;
		}		
	}
}

Result

5, 4, 1, 7, 10, 15,

That’s all for Partition a Linked List in Java, If you liked it, please share your thoughts in a comments section and share it with others too.