Partition List 分隔链表

Description

Given the head of 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.

将一个链表，按照给定的x值，分成2部分，链表前部小于x，后部大于等于x

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

思路: 虚头

新建链表a,b,并利用p遍历链表，将小于x的节点放入a，大于等于x的节点放入b，然后连接ab。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode bhead = new ListNode(0, null);//small
        ListNode ahead = new ListNode(0, null);//big
        ListNode atail=ahead,btail=bhead;
        ListNode p = head;
        ListNode q = null;
        while(p!=null){
            q = p.next;
            if (p.val < x) {
                p.next = atail.next;
                atail.next = p;
                atail = p;
            }
            else{
                p.next = btail.next;
                btail.next = p;
                btail = p;
            }
            p = q;
        }
        atail.next   = bhead.next;
        return ahead.next;
    }
}