3/7 算法题详解:Reverse a Singly Sublist 反转一个子单向链表


(smartpig) #1

本视频来自于北美CS刷题神器BitTiger Pro


单向链表真是一个有趣的东西,我们总是可以从单向链表方面找到一些有意思的问题,今天的问题就是单向链表节点间顺序调整问题的扩展。

下面是我们今天提出的问题的具体说明:给出一个单向链表L以及两个整数s和f,将链表L的第s个节点为头,以第f个节点为尾的子链表进行顺序的反转。其中链表L的节点从编号1开始的,比如头节点就是第一个节点。还有一个要求就是在实现过程中尽量不去申请额外的空间,这就意味着我们需要使用一些原地算法(in-place)的思路。

比如说我们给出如下图的链表L,并且s=2,f=5,那么返回的链表就需要像下图所示的链表一样。

![](data:image/svg+xml;utf8,)

由于给出的s=2,f=5,所以我们需要反转的子链表是从第2个节点到第5个节点,我们需要将这个子链表进行翻转,即将7-2-4-18的顺序变为18-4-2-7的顺序,并且不去变更链表的其他部分的顺序,然后返回一个新的链表。

也许你脑海中会立即浮现出一个想法就是我们先遍历整个链表,找到需要反转的子链表作为分隔链表,然后将这个子链表赋给一个新的链表后进行反转,最后把转换后的链表替换回原始的链表中。当然这是一种可行的方法,但是通过分析时间复杂度我们发现需要遍历链表两次,时间复杂度约是O(2n),而从空间复杂度来说如果链表L很长,f远大于s,就可能导致新申请的链表会很长,需要申请大量空间,那能只访问链表一遍并用最少的空间就实现这个功能吗?答案是肯定的。

接下来我们来说明一下我们提出的第二种优化后的方法。

Step 0:预处理

在处理过程中会出现一种特殊情况就是当s=1的时候,整个链表在反转后的头节点是会变的,然后去找新的链表的头节点就很难。为了避免这种情况发生,以便我们在返回链表的时候能够有一个确定的链表头节点,需要定义一个dummyHead(空头)节点来作为链表的头节点。定义一个curr指针来指向当前所在节点,将 dummyHead节点作为初始值赋给curr指针。如下图所示:

![](data:image/svg+xml;utf8,)

Step 1:遍历到s-1节点上

在这个步骤中,由于s值的给出,指示了子链表的头节点位置,所以需要将curr指针指向第s-1个节点上(单向链表中已知上一节点找下一节点很好找,但反向寻找却不易)。

在本例中s=2,所以我们需要将curr指针移到值为7的节点的前一个节点,即值为6的节点位置,如下图所示:

![](data:image/svg+xml;utf8,)

Step 2:为交换(swap)做准备

在这步中我们定义一个prev节点,把curr节点赋给prev,把curr节点移到下一个节点。如下图所示:

![](data:image/svg+xml;utf8,)

Step 3:(循环第一次)开始交换第一个节点

这里需要注意,交换数组中两个元素的位置很容易,但是在链表中要相当小心,一旦处理不得当,我们的链表将会断裂或者出现循环。首先定义一个temp节点,指向curr节点的next节点,然后把temp的next节点赋给curr的next节点,再把prev的next节点赋给temp的next节点,最后把temp赋给prev的next节点。将顺序从6-7-2-4-18变为6-2-7-4-18,交换了2和7的位置。参与交换的有三个节点,prev,curr,temp,每次循环执行的重点就是把temp节点,也就是最后面的那个节点交换到最前面来。稍微有点绕,可以借助下图帮助理解:

![](data:image/svg+xml;utf8,)

Step 4:(循环第二次)开始交换第二个节点

同上一步操作,顺序从6-2-7-4-18变为6-4-2-7-18,过程如下图所示:

![](data:image/svg+xml;utf8,)

以此类推,一直反转到第f个节点。

Step 5:返回结果

将子链表反转完成后,直接将dummyHead的下一个节点作为返回值,而不用考虑反转完成后新的链表的头节点是哪个节点。

完整实现代码如下:

![](data:image/svg+xml;utf8,)


本视频来自于北美CS刷题神器BitTiger Pro

每月更新的BitTiger Pro是一个覆盖了CS和数据科学方向最新高频面试题的精讲视频库。订阅后,你可以在Code Evaluation System亲自练习这道题。

![](data:image/svg+xml;utf8,)