Partition List

Sharing is caring!

Problem Statment
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.

Example

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
     public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }
         
        ListNode smallHead = new ListNode(0);
        ListNode small = smallHead;
         
        ListNode largereqHead = new ListNode(0);
        ListNode largereq = largereqHead;
        ListNode current = head;
         
        while (current != null) {
            if (current.val < x) {
                small.next = current;
                small = small.next;
            } else {
                largereq.next = current;
                largereq = largereq.next;
            }   
            
            current = current.next;
        }
         
         largereq.next = null;
         small.next = largereqHead.next;
         
         return smallHead.next;
    }
    
}