Question

link

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.

Stats

Frequency 3
Difficulty 3
Adjusted Difficulty 4
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is not very difficult, but can be confusing if the code don’t have good logic.

Solution

There is no fancy algorithm solution. I got it wrong in 10 submissions at first. After a few days, I did this problem again and passed with 1 attempt.

So just keep practicing.

Code

my code

public ListNode partition(ListNode head, int x) {
    if (head == null) return head;
    ListNode PH = new ListNode(1);
    PH.next = head;
    ListNode left = PH, preRight = PH, right = head;
    while (right != null) {
        if (right.val < x) {
            if (preRight != left) {
                preRight.next = right.next;
                right.next = left.next;
                left.next = right;
                left = right;
                right = preRight.next;
            } else {
                left = left.next;
                preRight = left;
                right = right.next;
            }
        } else {
            preRight = right;
            right = preRight.next;
        }
    }
    return PH.next;
}