LeetCoder - Partition List

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.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode partition(ListNode head, int x) {

        if(head==null) {

            return null;

        }

        ListNode small = null;

        ListNode big = null;

        ListNode cur = head;

        ListNode smallHead = null;

        ListNode bigHead = null;

        while(cur!=null) {

            if(cur.val<x) {

                if(small==null) {

                    small = cur;

                    smallHead = cur;

                } else {

                    small.next = cur;

                    small = cur;

                }

            } else {

                if(big==null) {

                    big = cur;

                    bigHead = cur;

                } else {

                    big.next = cur;

                    big = cur;

                }

            }

            cur = cur.next;

        }

        if(big!=null) {

            big.next = null;

        }

        if(small!=null) {

            small.next = null;

        }

        if(smallHead==null) {

            return bigHead;

        } else {

            small.next = bigHead;

            return smallHead;

        }

    }

}


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode p1 = dummy1;
        ListNode p2 = dummy2;
        ListNode p = head;
        while (p != null) {
            if (p.val < x) {
                p1.next = p;
                p1 = p1.next;
            } else {
                p2.next = p;
                p2 = p2.next;
            }
            p = p.next;
        }
        p1.next = dummy2.next;
        p2.next = null;
        return dummy1.next;
    }
}