运维开发网

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

运维开发网 https://www.qedev.com 2020-11-27 10:22 出处:51CTO 作者:帅地玩编程
前言以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。注:如果代码排版出现了问题麻烦通知我下,谢谢。【题目描述】给定一个单向链表的头结点head,节点的值类型是整型,再给定一个整数privot。实现一个调整链表的函数,将链表调整为左部分都是值小于privot的节点,中间部分都是值等于privot

前言

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

注:如果代码排版出现了问题麻烦通知我下,谢谢。

【题目描述】

给定一个单向链表的头结点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), 而且内部节点的顺序也是和原链表一样的。虽然思路简单,但在代码实现上也是有很多细节需要注意的,有时间的话希望大家动手打下码。

代码如下

 1//用三个指针处理,这道题主要是要注意串联链表时的一些细节处理
 2public static Node listPartition(Node head, int pivot) {
 3    Node sB = null;//小的指针头,即small begin
 4    Node sE = null;//小的指针尾,即 small end
 5    Node eB = null;//中的指针头,即 equal begin
 6    Node eE = null;//中的指针尾,即emall end
 7    Node bB = null;//大的指针头,即 big begin
 8    Node bE = null;//大的指针尾,即 big end
 9    Node next = null;//保存下一个节点
10    //进行划分
11    while (head != null) {
12        next = head.next;
13        head.next = null;
14        if (head.value < pivot) {
15            if (sB == null) {
16                sB = head;
17                sE = head;
18            } else {
19                sE.next = head;
20                sE = sE.next;
21            }
22        } else if (head.value == pivot) {
23            if (eB == null) {
24                eB = head;
25                eE = head;
26            } else {
27                eE.next = head;
28                eE = eE.next;
29            }
30        } else {
31            if (bB == null) {
32                bB = head;
33                bE = head;
34            } else {
35                bE.next = head;
36                bE = bE.next;
37            }
38        }
39        head = next;
40    }
41    //把三部分串连起来,串联的时候细节还是挺多的,
42    //串联的过程下面代码的精简程度是最学习的部分了
43
44    //1.小的与中的串联
45    if (sB != null) {
46        sE.next = eB;
47        eE = eE == null ? sE : eE;
48    }
49    //2.中的和大的连接
50    if (eB != null) {
51        eE.next = bB;
52    }
53    return sB != null ? sB : eB != null ? eB : bB;
54}

问题拓展

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

【题目描述】

【要求】

【难度】

未知。

【解答】

无。

往期

【链表问题】打卡6:三种方法带你优雅判断回文链表

【链表问题】环形单链表约瑟夫问题

【链表问题】如何优雅着反转单链表

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

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号