【链表】打卡7：将单向链表按某值划分成左边小，中间相等，右边大的形式

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。

【题目描述】

给定一个单向链表的头结点head，结点的值类型是整型，再给定一个整数privot。实现一个调整链表的函数，将链表调整为左部分都是值小于privot的结点，中间部分都是值等于privot的结点，右部分都是大于privot的结点。且对某部分内部结点的顺序不做要求。

例如:链表9-0-4-5-1，pivot=3。

调整后是1-0-4-9-5，

也可以是0-1-9-5-4

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

尉：★★☆☆

解答

方法一：可用数组，转换为荷兰国旗问题，但是需要额外空间，并且不具有稳定性。

方法二：使用三个辅助结点。

这道题在思路上还是比较简单的，但是在实现上还是有一些细节需要注意的。

本题对某部分的内部结点不做要求，一种很简单的方法就是用一个数组来存链表的结点，然后像类似于快速排序的分割函数那样，按照某个值把他们进行划分。

不过这样做的话，空间复杂度为 O(N)。我们也可以采取使用3个指针，把原链表依次划分成三个部分的链表，然后再把他们合并起来，这种做法不但空间复杂度为 O(1), 而且内部结点的顺序也是和原链表一样的。虽然思路简单，但在代码实现上也是有很多细节需要注意的，有时间的话希望大家动手打下代码。

代码如下

//用三个指针处理，这道题主要是要注意串联链表时的一些细节处理
public static Node listPartition(Node head,int privot){
    if(head == null || head.next == null){
        return head;
    }
    Node sB = null;//小于部分的指针头，small begin
    Node sE = null;//小于部分的指针尾，small end
    Node eB = null;//等于部分的指针头，equal begin
    Node eE = null;//等于部分的指针尾，equal end
    Node bB = null;//大于部分的指针头，big begin
    Node bE = null;//大于部分的指针尾，big end
    Node next = null;
    //分区
    while(head!=null){
        //使用next结点接管head后面的指针
        //如果直接使用head指针，会导致结点错乱
        next = head.next;
        head.next = null;
        if(head.value < privot){
            if(sB == null){
                sB = head;
                sE = head;
            }else{
                //不能使用sB.next = head，因为后面循环就是就是sB指向末尾了
                sE.next = head;
                sE = sE.next;
            }
        }
        if(head.value == privot){
            if(eB == null){
                eB = head;
                eE = head;
            }else{
                eE.next = head;
                eE = eE.next;
            }
        }
        if(head.value > privot){
            if(bB == null){
                bB = head;
                bE = head;
            }else{
                bE.next = head;
                bE = bE.next;
            }
        }
        head = next;
    }
    //把三部分串连起来，串联的时候细节还是挺多的，
    //串联的过程下面代码的精简程度是最学习的部分了

    //1.小的与中的串联
    if(sB != null){
        //这样子做更精简
        sE.next = eB != null ? eB : bB;
        //sE.next = eB;
        //为下部分做判断
        //eE = eE == null ? sE : eE;
    }
    //2.中的和大的连接
    if(eB != null){
        eE.next = bB;
    }
    return sB != null ? sB : eB != null ? eB : bB;
}

注意：分区时，记得断开原链表的next，否则后面再连接时判断是否为null时就会混乱。——代码实现中辅助结点next作用就是这个。

测试代码

public static void main(String[] args) {
    int[] arr = {0,99,-1,-20,50,18};
    Node head = new Node(arr[0]);
    Node node = head;
    int i = 0;
    while(++i<arr.length){
        node.next = new Node(arr[i]);
        node = node.next;
    }
    node = listPartition(head, 0);
    while(node!=null){
        System.out.print(node.value+" ");
        node = node.next;
    }
}