题解 | #划分链表#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    
    //双指针+尾插法
    public ListNode partition (ListNode head, int x) {
        if(head==null||head.next==null){
            return head;
        }
        // write code here
//构建哨兵
        ListNode numpy = new ListNode(x-1);
        numpy.next = head;
        ListNode nodePre = numpy;
        ListNode nodeNext = numpy.next;
        //找到nodePre<x 和 nodeNext>=x的值然后在中间不停插入
        while(nodeNext!=null){
            if(nodePre.val<x&&nodeNext.val>=x){
                break;
            }
            nodePre=nodePre.next;
            nodeNext=nodeNext.next;
        }
        
        while(nodeNext!=null){
             //nodeNext的下一个如果是小于x是不是就是要拿出来的值
            if(nodeNext.next!=null&&nodeNext.next.val<x){
                //找到要拿出来的值
                ListNode temp = nodeNext.next;
                //nodeNext断开与拿出来的值的联系
                nodeNext.next=nodeNext.next.next;
                //插入到nodePre 和 nodePre.next中间
                temp.next = nodePre.next;
                nodePre.next=temp;
                //这里很关键：如果不写这一步就是头插法，写了这一步就是尾插法
//假设：1 3 4 5 6 此时nodePre在1上， nodePre.next在3上，nodeNext.next是4，此时要将4插入1，3
//经历了上述代码以后1 4 3 5 6 此时nodePre在1上，nodePre.next在4上，当我要继续插入5的时候，是不是就会往1，4插
//但是如果跟新了nodepre为4以后，nodePre在4上，nodePre.next在3上，继续往里面插是不是就是插入在4后了，好好理解
                nodePre =nodePre.next;
            }
            else{
                //如果不满足，nodeNext继续找下一个节点
                nodeNext=nodeNext.next;
            }
        }
        return numpy.next;
    }
}