图解算法:单链表两两反转 | 眼睛会了手就会系列

3,912 阅读6分钟

一. 序

链表作为一种基本的数据结构,本身理解起来,很简单。它通过指针或者叫引用,将一组零散的内存空间(结点),串联起来组成一个数据存储结构。

链表根据其指针的指向和丰富程度,可以分为单链表、双向链表、循环链表、双向循环链表。其差别就是,是否在单链表的基础上为结点,增加更丰富的指针,让其实现更丰富的功能。

链表虽然很好理解,但是链表的代码,写起来却并不是那么容易,尤其上一些对单链表的操作,例如链表反转、链表双双反转、有序链表合并等。

你可以自己试试,放下手机拿起纸笔,来一场模拟面试,就是写一个单链表两两反转,看看能否一次通过。

写链表代码的时候,指针指来指去,很容易就把指针丢失,造成链表断裂。所以在操作链表时,其操作顺序就是我们着重关注的点。

虽然链表代码写起来不容易,但链表又是面试的常客,一些常见的算法实现,也是我们开发者必须要掌握的。

之前写过单链表反转的三种解法(戳我了解),今天再来聊聊它的升级版,链表两两反转,这也是 Leetcode 第 24 题,算是面试常客了。

二. 单链表两两反转

2.1 什么是单链表两两反转?

单链表反转比较好理解,就是逆序嘛,但是两两反转是什么意思呢?

我们知道,单链表是由指针,将一个一个结点串联起来的数据结构。那么我们将这些结点,两个为一组,在组内进行反转,就是两两反转了。

单链表两两反转这种题,非常适合用递归的思想来解决,将每一步操作都封闭在一个小单元内,然后重复操作。

通常递归能做的,循环也能做,所以我们就这两种解法,分别讲解。

2.2 循环解法

无论是使用循环还是递归,其实都是将链表结点交换的步骤拆解,放在一个个小循环(递归)中去处理。相对于递归,循环法在结点的使用步骤上更清晰,我们就以循环法作为切入点。

递归或循环,其核心就是找到抽象模型,在每个调用步骤中,不断重复相同的事情。

在单链表两两反转中,看似是在处理两个结点,但其实是在处理 4 个结点之间的关系。

除了待反转的 A、B 两个结点之外,还需要操作 A 的前驱结点 prev 结点和 B 的 Next 结点 b-next 结点。

我们每次反转,其实就在操作这四个结点,其中的操作步骤很重要。

如图所示,步骤 ① 操作有两步操作,因为其操作的指针互不影响,所以在写代码的时候不分先后,在保证 prev 指针和 b-next 指针的指向无错后,就可以开始 A、B 结点的反转,也就是步骤 ②。

最后我们只需要将我们关注的结点前移,就可以进入下一次循环。

在这个步骤中,我们在操作 4 个结点的指针,但是其实每次初始的结点,只有 A 的前驱结点 prev 结点。为了保证循环内的操作一致,我们可以在链表前,加一个虚拟的头结点,来辅助我们,让代码更简洁。

到这里,各个步骤就清晰了,每次反转两个结点,然后前移 dummy 指针。

最后,还需要再注意一些边界条件,注意我们的循环,什么时候停止。

在单链表两两反转的场景下,链表的结点数,有单有双,当结点数为单数时,最后一个结点已经找不到可以反转交换的结点了,此时保持不变即可。

接下来直接上循环代码了,这里使用我们熟悉的 Java 代码来实现。

public ListNode swapPairs(ListNode head){
  // 链表头增加虚拟结点 dummy
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  head = dummy;
  // 循环退出条件,注意链表结点数单双的情况
  while(head.next != null && head.next.next != null){
    // 开始反转
    ListNode a = head.next;
    ListNode b = a.next;
    head.next = b; // 步骤①
    a.next = b.next; // 步骤①
    b.next = a; // 步骤②
    // dummy 指针前移
    head = a;
  }
  return dummy.next;
}

代码中的注释已经很清晰了,首先在链表头插入一个虚拟结点 dummy,之后开启循环,循环退出的条件就是走到了链表尾部的边界,需要注意结点数为单、双两种情况。之后再按照前文中图解的步骤,开始操作链表指针实现两两反转,最后前移 dummy 指针。

2.3 递归解法

递归的解法,相对于循环解法,代码量上就少很多,看着也清爽了。主要是因为递归,通过一层层的调用,在方法栈上存储了存储了一些变量就是我们待操作的结点。

在这里,在递归里,我们依然关注三个问题,递归解决的小问题、终止条件以及返回值。

递归的解法,直接看代码比较清晰。

public ListNode swapPairs(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  ListNode next = head.next;
  head.next = swapPairs(next.next);
  next.next = head;
  return next;
}

再结合之前操作步骤的图解。

递归的方法比较绕,结合上图,找到思路,循环是一次从前向后的移动操作窗口,而递推是从后向前移动操作窗口。注意递归终止条件以及每次递归操作时,结点指针的轮转,多想多练就清晰了。

三. 小结时刻

到这里对单链表的两两反转,就讲解完毕。

写链表代码,除了考验逻辑思维能力,还考验编码能力,多写多练才是核心。

注意其中的边界条件以及每个操作单元中,结点指针的交换轮转。这其中的每个步骤的操作顺序,都通过图解的方式讲解清楚了,有疑问欢迎在留言去讨论。

本文对你有帮助吗?留言、转发、收藏是最大的支持,谢谢!


公众号后台回复成长『成长』,将会得到我准备的学习资料。