86. Partition List

Leetcode Linked List Two Pointers

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

分析

/**
 * 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.
 * <p>
 * You should preserve the original relative order of
 * the nodes in each of the two partitions.
 * <p>
 * Example:
 * <p>
 * Input: head = 1->4->3->2->5->2, x = 3
 * Output: 1->2->2->4->3->5
 * https://leetcode.com/problems/partition-list/description/
 *  
 * 这道题目看起来思路是非常简单的，就是要注意细节。
 * 解决方案是将大于x的元素放到另一个链表中，最后将两个链表连接起来。
 * 
 * 需要注意的有以下几点：
 * 1. 链表头部元素可能会大于x，为了方便，引入dummy node
 * 2. 要在新建链表尾部放null，很容易忘记
 * 
 * 
 * 
 */
public class Q86PartitionList {
    public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }

        // another list for nodes (node.val >= x).
        // add ListNode(0) as a dummy node
        ListNode head1 = new ListNode(0), head2 = new ListNode(0);
        head1.next = head;
        ListNode pos = head1.next, prev = head1, tmp = head2;

        while (pos != null) {
            // find notes, whose value if greater or equal than x,
            // then remove them from head1 and put them in head2 in order,
            if (pos.val >= x) {
                // put it in head2
                head2.next = pos;
                head2 = head2.next;
                // remove it from head
                prev.next = pos.next;
                // prev unchanged; no code
            } else {
                // change prev
                prev = pos;
            }

            // change pos
            pos = pos.next;
        } // end while

        // 别忘了结束链表
        head2.next = null;
        prev.next = tmp.next;
        return head1.next;
    } //end method partition
} // end class