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.

这道题按要求将所有的小于给定x的node全部放到左边并且需要保持原来的顺序,我们只需要在左边找到第一个不小于x的node,然后记下位置tail,剩下的node只要扫描到小于x的值就append到之前那个tail之后即可。
逻辑很简单,就是要注意1. 用一个helper指向head,避免head本身被替换的情况,2. 交换两个node的时候需要记下两个一个tail一个curr的next指向存进临时变量中。

/**
 * 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) // empty list
            return head;
        ListNode helper = new ListNode(Integer.MIN_VALUE); // helper points to head
        helper.next = head;
        ListNode tail = helper;
        //find last one that is less than x
        while(tail.next.val < x)
        {
            tail = tail.next;
            if (tail.next == null) // nothing greater or equal to x
                return head;
        }
        
        ListNode pre = tail.next;
        ListNode curr = pre.next;
        while(curr != null)
        {
            if (curr.val < x) // need to move
            {
                ListNode t1 = tail.next; // store the next node that is going to be replaced
                ListNode t2 = curr.next;
                tail.next = curr;
                curr.next = t1;
                pre.next = t2;
                tail = curr;
                curr = pre.next;
            }
            else
            {
                pre = pre.next;
                curr = curr.next;
            }
        }
        return helper.next; // incase head was replaced
    }
}
/**
 * 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) {
        ListNode helper = new ListNode(-1);
        helper.next = head;
        ListNode scan = helper;
        ListNode tail = helper;
        //find the first node that is >= x
        boolean found = false;
        while(tail.next != null) {
            if (tail.next.val >= x) {
                found = true;
                break;
            }
            tail = tail.next;
            scan = scan.next;
        }
        if (!found) // if everything besides the last node is less than x
            return head;
        while(scan.next != null) {
            if (scan.next.val < x) {
                ListNode t1 = tail.next;
                ListNode t2 = scan.next.next;
                tail.next = scan.next;
                tail = tail.next;
                tail.next = t1;
                scan.next = t2;
            }
            else
                scan = scan.next;
        }
        return helper.next;
    }
}

Swap the node instead of swaping the value,

/**
 * 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) {
        ListNode helper = new ListNode(Integer.MIN_VALUE);
        helper.next = head;
        ListNode p = helper;
        ListNode s = helper;
        while(s.next != null) {
            if (s.next.val < x) {
                if (p != s) {
                    ListNode tmp1 = p.next;
                    p.next = s.next;
                    ListNode tmp2 = s.next.next;
                    s.next.next = tmp1;
                    s.next = tmp2;
                }
                else
                    s = s.next;
                p = p.next;
            }
            else
                s = s.next;
        }
        return helper.next;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s