题解 | #链表分割#

思路：

先读题，题中给一个x值，我们需要将链表通过给的值，左右分别放入小于x的数，和大于x的数。
可以这样操作，new两个链表，一个链表放入小于x的数，一个链表放入大于x的数，最后将两个链表进行链接。
链接细节：若 左表为nul，那么我们直接返回右边的头；若左边不为空，我们只需将右表的头，通过尾插法插入到左表的尾。在此之前，我们还需要判断右边的尾节点的nxet是否为空，不为空，我们需要手动制空。不然和出来的链表会带环。
import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode cur=pHead;
        //左边
        ListNode leftHead=null;
        ListNode left=null;
        //右边
        ListNode rightHead=null;
        ListNode right=null;
        //判断存左还是存右
        while(cur!=null) {
            if(cur.val<x) {
                if(left==null) {
                    left=cur;
                    leftHead=cur;
                }else {
                    left.next=cur;
                    left=left.next;
                }
            }else {
                if(right==null) {
                    right=cur;
                    rightHead=cur;
                }else {
                    right.next=cur;
                    right=right.next;
                }
            }
            cur=cur.next;
        }
        //判断左是否为空
        if(leftHead==null) {
            return rightHead;
        }
        //连接两个链表
        left.next=rightHead;
        //判断右边尾结点next是否为空（若不是空，又没进行手动改空，链表会有环）
        if(right!=null) {
            right.next=null;
        }
        return leftHead;
    }
}