个人技术分享

一:题目

二:思路讲解

将小于x的放进一个新的链表,将≥x的也放进另一个新链表。

然后 第一个新链表的尾节点的next链接到第二个新链表的哨兵节点的next,因为本身不存在哨兵位。

最后 链接完成后的链表的最后一个节点的next一定要置空,因为该节点在一开始的链表中的next是有指向的,而他是最后一个,它的指向没被改变,有可能会造成死循环,成环!

ghead 和 gtail 为>=x的链表的哨兵位,lhead 和 ltail 为<x的链表的哨兵位

1:根据x形成两个新链表

2:两个链表的 连接

需要注意的是:ltail这个尾节点连接的ghead的下一个节点,而不是ghead这个节点,因为两个链表的哨兵位是我们创建的,后面都会被释放。

3:将新链表的尾节点gtail的next一定要置空

否则可能出现以下情况:

因为: 

该尾节点在一开始的链表中的next是有指向的,而他是最后一个,它的指向没被改变,有可能会造成死循环,成环!

代码展示:

 

最后需要注意的是:

两个链表拼接到一起的新链表的头指针,不是哨兵位,而是哨兵位的下一个节点,因为题目给的链表不存在哨兵位,哨兵位只是我们方便自己进行操作。

哨兵位的优势:

就算小于x或者大于等于x的链表为空,它都可以直接使用

其次优势: 

第一次的插入,不需要再去判断两个链表的head和tail是否为空,然后再去进行额外的操作。