划分链表

方法一：创建两个表之后进行连接

思路：

1.创建两个表的虚的头节点

2.遍历原先的表，将大于等于x的节点找出来连在存大的节点的表中，将小于x的节点找出来连在用于存小于x的节点的表中

3.再将两个表进行连接

代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode partition (ListNode head, int x) {
        //由于要将两个表进行划分区间，将节点划分为两个表
        //所以对于创建新的节点，为了方便操作，需要创建两个虚的头结点
        //由于之后需要用到两个虚的节点，所以需要保留这两个值，用cur1和cur2进行操作
        ListNode dummynode1=new ListNode(-1);
        ListNode cur1=dummynode1;
        ListNode dummynode2=new ListNode(-1);
        ListNode cur2=dummynode2;
        //遍历链表：只要链表不为空，就继续进行
        while(head!=null){
            //将小于x的节点连接在用于存小值的表中
            if(head.val<x){
                cur1.next=head;
                cur1=cur1.next;
            }else{
                //将大于等于x的节点连接在存大值的表中
                cur2.next=head;
                cur2=cur2.next;
            }

            head=head.next;
        }
        //将大的节点的尾指针指向空，再将大节点的尾指针指向长节点的头节点处
        cur2.next=null;
        cur1.next=dummynode2.next;
        //返回头结点
        return dummynode1.next;

    }
}

方法二：求出插入区间的左右端点

思路：

1.在原来的表头连接一个虚的头结点

2.遍历区间找到插入区间的左右端点

3.再从插入区间的右端点进行查找小于x的节点，将这些节点插入到区间中

代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode partition (ListNode head, int x) {
        //由于用双指针定位需要插入的区间的左右端点，但是由于可能第一个节点是大于等于x，那么就需要找到小于x的点插入第一个节点之前
        //由于对于在第一个节点前插入节点与在两个节点中插入是不一样的操作，所以可以设置一个虚的头结点，不要忘记连在原链表的头结点上！！
        //总结：对于在原链表上进行删除和插入节点的操作，就需要再链表的最前面设置一个虚的头结点，并且将虚的头结点连在原链表的表头的节点上！！对于创建一个新的表的时候，只需要设置一个虚节点即可，不需要进行连接节点的操作
        ListNode dummynode=new ListNode(-1);
        dummynode.next=head;
        ListNode left=dummynode;
        //设置一个左指针，向后找，只有当发现该节点的下一个节点的值大于等于x，就表示这个节点的下一个节点就是等会
        //找到小于x的节点插入的位置的右端点，即小于等于x的值是插入在该右端点的左边
        //而此时的left就是插入区间的左端点
        while(left.next!=null&&left.next.val<x){
            left=left.next;
        }
        ListNode right=left.next;
        ListNode p=right;
        //接下来从插入区间的右端点开始遍历，找到小于等于x的节点，将它插入区间中，并在原位置删除，注意指针操作的顺序
        //之后更新区间的左端点，因为之后找到小于等于x的点就是插在最新的刚插入的节点的后面的位置
        while(p!=null&&p.next!=null){
            if(p.next.val<x){
                left.next=p.next;
                p.next=p.next.next;
                left.next.next=right;
                left=left.next;
            }else{
                 p=p.next;
            }
        }
        return dummynode.next;
    }
}