链表训练6：将单向链表按某值划分成左边小，中间相等，右边大的形式

【题目描述】

给定一个单向链表的头结点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 pivot) {
        Node sB = null;//小的指针头，即small begin
        Node sE = null;//小的指针尾，即 small end
        Node eB = null;//中的指针头，即 equal begin
        Node eE = null;//中的指针尾，即emall end
        Node bB = null;//大的指针头，即 big begin
        Node bE = null;//大的指针尾，即 big end
        Node next = null;//保存下一个节点
        //进行划分
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (sB == null) {
                    sB = head;
                    sE = head;
                } else {
                    sE.next = head;
                    sE = sE.next;
                }
            } else if (head.value == pivot) {
                if (eB == null) {
                    eB = head;
                    eE = head;
                } else {
                    eE.next = head;
                    eE = eE.next;
                }
            } else {
                if (bB == null) {
                    bB = head;
                    bE = head;
                } else {
                    bE.next = head;
                    bE = bE.next;
                }
            }
            head = next;
        }
        //把三部分串连起来，串联的时候细节还是挺多的，
        //串联的过程下面代码的精简程度是最学习的部分了

        //1.小的与中的串联
        if (sB != null) {
            sE.next = eB;
            eE = eE == null ? sE : eE;
        }
        //2.中的和大的连接
        if (eB != null) {
            eE.next = bB;
        }
        return sB != null ? sB : eB != null ? eB : bB;
    }

问题拓展

思考：如果给你的是一个环形链表，让你来划分，又该如何实现呢？

如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人，帅地正在疯狂更新中….

帅地永久会员

收藏 海报 分享链接