leetcode86.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的值放在前面，大于等于x的值放在后面，移动的过程中不改变数字之间的相对顺序。

思路一：移动节点

该思路需要我们记录3个节点。当前节点的前一个节点currentPrev,插入位置的前一个节点prev，以及记录初始位置的节点start。当发现一个需要交换的节点时，先获得这个节点，然后将currentPrev指向节点的后一个节点。之后将当前的节点插入到prev之后。代码如下：

public ListNode partition(ListNode head, int x) {
    if(head==null || head.next==null){
        return head;
    }
    ListNode start = new ListNode(0);
    ListNode prev = new ListNode(0);
    ListNode currentPrev = new ListNode(0);
    start.next = prev;
    prev.next = head;
    currentPrev.next = head;
    while(currentPrev.next!=null && currentPrev.next.val<x){
        currentPrev = currentPrev.next;
        prev = prev.next;
    }
    while(currentPrev!=null && currentPrev.next!=null){
        int val = currentPrev.next.val;
        if(val < x){
            ListNode temp = currentPrev.next;
            currentPrev.next = currentPrev.next.next;
            temp.next = prev.next;
            prev.next = temp;
            prev = prev.next;    
        }else{
            currentPrev = currentPrev.next;
        }
    }
    return start.next.next;
}

思路二：使用两个链表

我们设置两个头指针当做两个链表，当遇到的数值小于x，则加入第一个链表，否则加入第二个链表。最后将两个链表连接。代码相比于第一种更加清晰一些。

public ListNode partition2(ListNode head, int x) {
    if (head == null || head.next == null) return head;
    
    ListNode dummy1 = new ListNode(0);
    ListNode dummy2 = new ListNode(0);
    ListNode curr = head, first = dummy1, second = dummy2;
    while (curr != null) {
        if (curr.val < x) {
            first.next = curr;
            first = first.next;
        } else {
            second.next = curr;
            second = second.next;
        }
        curr = curr.next;
    }
    first.next = dummy2.next;
    second.next = null;
    return dummy1.next;
}