86. Partition List

Description

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input:

head = 1 -> 4 -> 3 -> 2 -> 5 -> 2,

x = 3

Output: 1 -> 2 -> 2 -> 4 -> 3 -> 5

Solutions

ListNode

// Definition for singly-linked list.
public class ListNode {
	int val;
	ListNode next;
	
	ListNode() {}
	
	ListNode(int val) { this.val = val; }
	
	ListNode(int val, ListNode next) { 
		this.val = val; 
		this.next = next;
	}
}

Solution 1

/**
 * Time complexity : O(N), where N is the number of nodes in the original linked 
 *    list and we iterate the original list.
 * Space complexity : O(1), we have not utilized any extra space, the point to 
 *    note is that we are reforming the original list, by moving the original 
 *    nodes, we have not used any extra space as such.
 */

class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null) return head;
        
        ListNode smaller = new ListNode(0);
        ListNode smallerHead = smaller;
        ListNode greater = new ListNode(0);
        ListNode greaterHead = greater;
        
        while(head != null) {
            if(head.val < x) {
                smaller.next = head;
                smaller = smaller.next;
            } else {
                greater.next = head;
                greater = greater.next;
            }
            head = head.next;
        }
        
        greater.next = null;
        smaller.next = greaterHead.next;
        
        return smallerHead.next;
    }
}

Follow up

• Traverse Linked List from middle to left-right order using recursion - GFG