Leetcode | 第3节：链表

学弱猹

发布于 2021-08-10 11:20:17

2620

发布于 2021-08-10 11:20:17

文章被收录于专栏：学弱猹的精品小屋学弱猹的精品小屋

这一篇文章我们来总结一下链表（LinkedList）相关的问题。

链表是非常重要的一种数据结构，它的好坏处我们不讳言，毕竟这是在考写代码不是在考System Design2333，但是链表其实也很麻烦，学过链表的就知道，在链表中做添加，删除等等，是需要注意很多细节的。因此有必要单独开一个专题说一下。

那么我们开始吧。

数据结构1：链表

这个系列不是为初学者准备的，但我们还是简单介绍一下链表。大家都知道数组（Array）这个数据结构，它有一些特点，就是访问随机（根据索引访问，所以是常数级别复杂度），但是删除，插入会比较慢（如果要保证连续性的话）。反过来，链表的话，就是没有顺序要求，插入删除什么的会比较快，但是查找就会慢了。

一个比较好的链表的示意图如下。

这里每一个结点有一个值，对应一定存储空间，可以通过删除啊，插入啊等方式来改变他们的连接状态。当然你也可以看出，访问后一个元素之前，必须要先访问前一个，例如这里如果要访问3，就必须先访问1和2，所以查找就会慢了。

关于链表的插入，删除等操作，都是比较标准的数据结构课的内容。因为这一个系列以Leetcode为主，所以我们就不多说这一块了。

好的，我们来看具体的题目吧。

Problem 1: Leetcode 445 给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。

一个好的例子是，如果输入的两个链表分别为7 -> 2 -> 4 -> 3和5 -> 6 -> 4，那么答案应该就是7 -> 8 ->0 -> 7，列个竖式算一下应该就能看出来了。

这一个题目的关键在于，我们链表的访问顺序和实际的做竖式的方式是反过来的。因此有什么办法能够逆转这个方式，就比较重要。能够做到逆转的，除了信条（TENET）以外，就是栈（Stack）这个数据结构了。

剩下的我们就不多说了，把数字放到栈之后，剩下的事情就是把它一个一个取出来，按照加法原则来做就好。我们给出核心代码。

// Push the elements into stacks
stack<int> s1, s2;
while (l1) {
  // Shows how to visit every elements in a linkedlist
  s1.push(l1 -> val);
  l1 = l1 -> next;
}
while (l2) {
  s2.push(l2 -> val);
  l2 = l2 -> next;
}
int carry = 0;
ListNode* ans = nullptr;

// Add two numbers
while (!s1.empty() or !s2.empty() or carry != 0) {
  int a = s1.empty() ? 0 : s1.top();
  int b = s2.empty() ? 0 : s2.top();
  if (!s1.empty()) s1.pop();
  if (!s2.empty()) s2.pop();
  int cur = a + b + carry;
  carry = cur / 10;
  cur %= 10;
  auto curnode = new ListNode(cur);
  curnode -> next = ans;
  ans = curnode;
}

好吧，这个题更像是一个栈的技巧的题目。但至少你可以通过它复习一下链表的访问方式，也不算白看对吧……

Problem 2: Leetcode 160 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

用下图举例。

对于这个例子而言，它们就是在8相交的。

这个题的做法其实和链表操作也没什么关系，它是一道数学题……如果我们设属于

但是不相交的部分的长度为

，属于

但是不相交的部分的长度为

，相交的部分的长度为

，那么这样的话，只要保证设计的方案，能够使得链表的指针分别从

A, B

出发，最终同时到达相交点就可以了。而事实上，两个结点都走

a + b+ c

步就可以完成这个任务。具体方案就是

定义两个指针，分别从

A, B

的头结点出发，若

出发的指针变成了空，则把它放到

的头结点，反之类似。直到两个指针指向同一个结点或指向空，则返回。

这个方案可以成功的原因在于，如果有相交，只要每一次走一步，最终走了

a+b+c

步的时候，两个指针一定在同一个位置/一定同时为空。并且可以看出，这覆盖了

a = b

和两个链表不相交的情况，感兴趣的朋友可以想想为什么。

当然，有人会反驳说，我根本不知道

a, b, c

是多少，我怎么用这个方案？这里要注意的是，我们并不是要说每个节点都要走

a + b +c

步，而是说，每一个结点经过有限步，一定会遇到同一位置/同时为空的情况。所以你不用担心太多，走就完事了。

好的，我们放出核心代码。

if (headA == null || headB == null) {
  return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
  pA = pA == null ? headB : pA.next;
  pB = pB == null ? headA : pB.next;
}

最终返回pA或者pB就可以了。

Problem 3: Leetcode 24 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

这里的“节点交换”的含义是，因为每一个节点的地址是不同的，所以仅仅是赋值不同，和真正意义上去改变连接的方式，是有很大的差别的。

比方说我们一开始的结果是[1, 2, 3, 4]，那么最后的结果应该是[2, 1, 4, 3]，可以看出，1, 2交换了顺序，3, 4交换了顺序。

这一个题我们讲两个方法，首先来看看递归。如果一个问题可以用递归来完成，那么重要的点就在于，它是否具有一套统一的方法。在这里可以看出，我们如果只看1, 2和只看3, 4，我们其实只需要关注两件事：1, 2如何翻转，怎么与下一个连接。对于3, 4，其实要做的事情也类似，所以我们只需要解决了一个子问题，之后的问题自然就解决了，所以递归在这里是可用的。

为了解释，我们先放出代码，然后画一张图。

ListNode* swapPairs(ListNode* head) {
  if (head == nullptr || head->next == nullptr) {
    return head;
  }
  ListNode* newHead = head->next;
  head->next = swapPairs(newHead->next);
  newHead->next = head;
  return newHead;
}

所以可以看出，我们并不关心全过程应该去怎么做，而只关心一个小的部分。这就是把问题做了一种合理的拆解。

当然也要注意边界条件，如果我们已经到了末尾，那么就不需要再做更改了。

第二个方法是迭代。就像我们在动态规划系列（链接）中，曾经把一个递归的方法改成了循环的方法。这就是改成了迭代法。迭代法的思路其实是类似的，就是先给出头指针，再保存头指针的下一个指针和下下个指针（如果不保存下下个，那么你修改完之后，就没办法访问到下一组节点了）。

我们放出它的核心代码。事实上，这个方法的核心步骤和递归法无差，大家将代码对着图看，就能比较好的理解了～

ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode temp = dummyHead;
while (temp.next != null && temp.next.next != null) {
  ListNode node1 = temp.next;
  ListNode node2 = temp.next.next;
  temp.next = node2;
  node1.next = node2.next;
  node2.next = node1;
  temp = node1;
}
return dummyHead.next;

注意这里实际上是把temp当成了dummyHead，所以修改temp的信息的时候，也会修改掉dummyHead。

Problem 4: Leetcode 206 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

反转链表应该是相当经典的高频题了，直到今天都还是这样。

具体应该怎么做呢？答案其实也分两种：递归和迭代。不过这一个题之后，我们节省空间，就不放两个方法了。

先看递归方法，还是一样，我们反转的时候，其实本质上就是把链表的连接方式调一个顺序。所以假如说我们要反转1, 2, 3，那么第一步肯定是要关心，1应该指向哪里，1之后的部分怎么指向1，所以我们的代码和图就是这样的。

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

对于迭代法也是类似的，但需要额外考虑一下，究竟应该保存链表的哪些节点。这里我们要保存的是它的前一个和后一个。这是因为前一个是它所要指向的位置（反转了），后一个是下一次循环遍历需要到达的初始位置。

好的，我们也放出核心代码。

ListNode* reverseList(ListNode* head) {
  ListNode* prev = nullptr;
  ListNode* curr = head;
  while (curr) {
    ListNode* next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

当然了，反转链表的进阶题目还是很多的，这里推荐大家看一看Leetcode 24和25。当然，它们在设计上会更精巧一些，读者可以拿来做练习，也可以看题解找找思路。

Problem 5: Leetcode 21 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

这一个题目也是算法与数据结构的必考题了，当然它也必然是高频题的一部分了。

这一个题思路非常直接。我们给出两个指针，指针分别指向两个链表的初始位置（比如说

l_1, l_2

），然后再建立一个虚拟的头结点，用于表示整个新的链表的头结点（这里要注意一个细节，这个头结点没有value，所以返回链表的时候要注意返回它的next。很多时候有头结点都会使得我们的思考更方便）。

好的，因为每一个链表都是升序的，所以自然可以通过比较两个链表目前结点的值，来确定究竟我们的头结点应该往哪里走。而比较完之后，自然就需要改变两个链表所在位置。具体来说，假如说我们发现l1 -> val <= l2 -> val，就说明新的链表的下一个结点应该是

l_1

，那么这个时候改变指向之后，就应该让

l_1

走到下一个结点，也就是l1 = l1 -> next。

这一过程用图来表示大概如下

好的，我们来放出核心代码

ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
    if (l1->val < l2->val) {
        prev->next = l1;
        l1 = l1->next;
    } else {
        prev->next = l2;
        l2 = l2->next;
    }
    prev = prev->next;
}

// 合并剩下的链表
prev->next = l1 == nullptr ? l2 : l1;

return preHead->next;

注意在这里有一个细节，就是一定会有某一个时刻，

l_1, l_2

中枚举到了最后的结点，那么剩下的结点只需要自然拼接到最后就可以了。

Problem 6: Leetcode 92 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

比方说如果head = [1,2,3,4,5], left = 2, right = 4，那么实际上，就是把中间的2, 3, 4做个反转，再和前后连起来就可以了。

关于反转，我们当然可以利用之前Problem 4（Leetcode 206）的方法，将对应的位置拿出来先做反转，然后再前后相连。但是这里我们介绍一种一次遍历的方法，会更有实用性一些。

我们以这里的案例为例，现在考虑一下，所谓的反转，就是一开始是2 -> 3，现在要变成3 -> 2。那么很明显，这一步做完之后还需要考虑到走到下一步，因此之后的那个4也不能放过。同时为了保证最终我们的left之前的那一个元素，指向的是要改变的一段中，最后的元素，我们还需要额外处理一下。用图来说，就是

用文字来模拟一下，就是

2 -> 4
3 -> 2
1 -> 3

这样就会变成1, 3, 2, 4, 5。然后所有元素往后动一动，就变成了

2 -> 5
4 -> 3
1 -> 4

当然你可以继续写，你会发现这个过程，每一步只有4个结点参与，分别是left开头的3个结点和left的前一个结点。然后执行结束之后，让left开头的3个结点位置分别后移一格就可以了。

好的，我们来放出核心代码。这里要注意的是核心代码的逻辑如果单看，也是很复杂的。我们推荐大家在写代码或者看代码之前，先理一理相关的思路，看是否与分析一致。这样的话也不容易出错。

ListNode *dummyNode = new ListNode(-1);
dummyNode->next = head;
ListNode *pre = dummyNode;
for (int i = 0; i < left - 1; i++) {
    pre = pre->next;
}
ListNode *cur = pre->next;
ListNode *next;
for (int i = 0; i < right - left; i++) {
    next = cur->next;
    cur->next = next->next;
    next->next = pre->next;
    pre->next = next;
}
return dummyNode->next;

这里我们依然设置了一个虚拟的头结点，所以返回的时候记得返回next。

Problem 7: Leetcode 61 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

这里举个例子，就是假如说一开始的结果是1, 2, 3, 4, 5，然后旋转了一次，就会变成5, 1, 2, 3, 4，再旋转一次，就会变成4, 5, 1, 2, 3。所以如果k = 2，那么答案就是4, 5, 1, 2, 3。

对于这个问题，我们按照上一个题一样的思路来思考。对于这个案例，我们可以思考一下，大概是这么一个流程

5 -> 1
4 -> null

这里的1其实可以认为是head -> next

然后再旋转一次的话，就是

4 -> 5
3 -> null

这里的5也恰好是head -> next。

这个思路自然非常直接，但是也有明显的问题，就是它每一次，都需要依赖链条中的倒数第二个元素，而这个元素是没办法通过next什么的来进行实时追踪的。比方说你第一次需要改变结点4，你是没有办法在这一步保存结点3的，因为**4并不指向3**，除非从头到尾遍历一遍找到这个位置，但是很明显这样就大大增加了时间复杂度。

为了解决这个问题，有一个方案就是断环。我们可以把这一条链表做成一个环，然后寻找它可以断的位置。假如说不做旋转，对应k = 0，那么只需要在5 -> 1断一下就可以了。如果我们头结点是1，那么相当于要移动头结点4次（得到5），然后再返回这个结点的next。如下图。

类似的，如果k = 1，那么就是断4 -> 5，那么移动3次就可以了。所以移动的次数其实有一个公式，就是

(n - 1) - k \mod n

。这里

是链表的长度。

好的，我们来看看核心代码。

if (k == 0 || head == nullptr || head->next == nullptr) {
    return head;
}
int n = 1;
ListNode* iter = head;
while (iter->next != nullptr) {
    iter = iter->next;
    n++;
}
int add = n - k % n;
if (add == n) {
    return head;
}
iter->next = head;
while (add--) {
    iter = iter->next;
}
ListNode* ret = iter->next;
iter->next = nullptr;
return ret;

代码的前两行是边界条件，这也是要时刻注意的点。面试中忽略了边界条件，也是会被扣分的。

Problem 8: Leetcode 141 给定一个链表，判断链表中是否有环。

环形链表什么样，其实我们在Problem 7已经见过了。在这里如果我们可以找到环，那么容易发现，无论你走多少步，都会在这个环中去绕来绕去。那么一个很直接的思路就是使用哈希表，简单来说，一直往前走，将每一个元素（注意：这里指的是保存链表的地址，不是链表的元素值）都加入到哈希表中。这样的话，等我们绕了环一圈之后，回到原点了，在哈希表中就能够找到这个元素。那么只要能找到，就说明有环。反过来，遍历结束了都没有找到重复的元素，就说明没有环。

这个思路直接也比较容易实现，但是需要消耗一定的存储空间。所以更好的思路是快慢指针。这个方法还是有一些地方会再次遇到的，所以我们介绍一下。

一个简单的事实是：如果是在一条直路上，那么一个跑得快的生物一定会一直在一个跑得快的生物的前面。反过来，如果在一个环上，唯一的可能就是跑得快的生物不停的套圈跑得慢的生物。所以事实上只需要做一件事情，就是使用两个指针，让一个跑的快一点，一个跑的慢一点，再看什么时候，快的指针套圈了，就可以了。

好的，我们放出核心代码。

if (head == nullptr || head->next == nullptr) {
    return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
    if (fast == nullptr || fast->next == nullptr) {
        return false;
    }
    slow = slow->next;
    fast = fast->next->next;
}
return true;

在这里，slow相比较fast，就是跑的会慢一些（一个一次走一步，一个走两步）。所以如果一开始fast在前面，结果两个撞上了，就是fast追上了slow，那么自然就说明套圈了，也就说明出现了环。

小结

本节我们主要介绍了一些比较常规而高频的链表题。内容不是很多，是因为对于链表的考察更多的是设计能力而不是算法能力，因此我们没有把涉及到其他算法的题目放在这一个系列。当然大家可以看到，遇到链表相关的题目，画图一定是最重要的事情。先画图再思考代码逻辑，才不会感到混乱。

下一节我们给大家介绍查找和排序相关的问题。事实上二分和排序也有一些刷题常见的tricks，所以我们还是有必要单独拉出来说一些的~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-07-05，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

编程算法

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数据结构

编程算法

登录后参与评论

0 条评论

热度