LeetCode_86 分隔链表（链表题）

题目地址：https://leetcode-cn.com/problems/partition-list/description/

题目：

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

---

试题分析：

该题要抓住几个要点，第一是只需要进行分隔不需要排序；第二要在两个分区中保留原先初始相对位置。正是因为这两点可以让分区算法做到O（n）的时间复杂度。整个算法的核心思路是遍历真哥哥链表，当遇到比比比较值大的节点，则加到一个新链表中，同时修改原链表连接。整个过程中需要记录小数链表头和大数链表头用于遍历结束后进行大小链表拼接，还需要记录小数前置和大数前置节点用于修改链表。总的来说这道题思路不难，但是需要熟练操作链表，不然很容易导致链表操作错误。

代码：

public ListNode partition(ListNode head, int x) {
        
        //创建虚拟头节点简化后面链表修改操作，不用考虑头节点的特殊操作
        ListNode newHead = new ListNode(0);
        ListNode bigHead = new ListNode(0);
        newHead.next = head;
        ListNode smallPre = newHead;
        ListNode bigPre = bigHead;
        ListNode p = head;
        while(p!=null){
            if(p.val<x){
                //当循环节点小于比较值则小数前置节点后移一位
                smallPre = smallPre.next;
                p = p.next;
            }else{
                //大数前置的next连接到复合条件的处理节点
                bigPre.next = p;
                //大数前置节点后移一位
                bigPre = bigPre.next;
                //小数前置next指向处理节点的next节点
                smallPre.next = p.next;
                p = p.next;
            }
        }
        bigPre.next = null;
        //小数链表尾和大数链表头的next对接（去掉大数虚拟头节点）
        smallPre.next = bigHead.next;
        return newHead.next;
    }

源码路径：com.monkey01.linkedlist.PartitionList_86

配套测试代码路径：test目录com.monkey01.linkedlist.PartitionList_86Test

https://github.com/feiweiwei/LeetCode4Java.git