Python蓝桥杯训练：基本数据结构 [链表]

Python蓝桥杯训练：基本数据结构 [链表]

本次博客我是通过Notion软件写的，转md文件可能不太美观，大家可以去我的博客中查看：北天的 BLOG，持续更新中，另外这是我创建的编程学习小组频道，想一起学习的朋友可以一起！！！

一、链表理论基础知识

链表是一种特殊的数据结构，它是由节点（node）组成的。每个节点都存储了一个数据元素和一个指向下一个节点的指针。指向最后一个节点的指针是空的。因此，我们可以从第一个节点开始，通过沿着指针移动到下一个节点，直到到达最后一个节点为止。

链表有两种类型：单向链表和双向链表。在单向链表中，每个节点只指向下一个节点，而在双向链表中，每个节点都指向下一个节点和前一个节点。

链表具有动态内存分配，因此我们可以在不需要预先知道链表大小的情况下在链表中插入或删除元素。

在 Python 中，我们可以使用类来实现链表。每个节点可以是一个类的实例，其中包含数据元素和指向下一个节点的指针。

操作链表的常见任务包括插入节点、删除节点、查找节点、遍历链表等。

常用的链表操作有单链表、双向链表、循环链表、双向循环链表等。

下面我们来简单的介绍一下单链表、双向链表、循环链表、双向循环链表：

• 单链表：在单链表中，每个节点只包含一个指向下一个节点的指针。指向最后一个节点的指针是空的。
• 双向链表：在双向链表中，每个节点都包含一个指向下一个节点的指针和一个指向前一个节点的指针。
• 循环链表：在循环链表中，最后一个节点的指针不是空的，而是指向第一个节点。因此，我们可以从任何节点开始，通过沿着指针移动到下一个节点，直到回到第一个节点为止。
• 双向循环链表：双向循环链表是循环链表的双向版本，即每个节点都包含一个指向下一个节点的指针和一个指向前一个节点的指针，并且最后一个节点的指针指向第一个节点，第一个节点的指针指向最后一个节点。

二、有关链表的一些常见操作

• 插入：在链表的任意位置插入新节点

  # 节点类
  class Node:def __init__(self, data):self.data = dataself.next = None# 链表类
  class LinkedList:def __init__(self):self.head = None# 在指定位置插入一个新节点def insert_at_pos(self, pos, data):# 创建一个节点new_node = Node(data)# 如果链表为空if self.head is None:self.head = new_nodereturn# 如果位置为0，则在开头插入if pos == 0:new_node.next = self.headself.head = new_nodereturn# 遍历链表找到位置temp = self.headcount = 0while temp is not None:if count == pos - 1:breaktemp = temp.nextcount += 1# 插入节点new_node.next = temp.nexttemp.next = new_node
  

• 删除：从链表中删除指定的节点

  # 节点类
  class Node:def __init__(self, data):self.data = dataself.next = None# 链表类
  class LinkedList:def __init__(self):self.head = None# 删除指定数据的节点def delete_node(self, data):# 如果链表为空if self.head is None:return# 如果头节点有数据if self.head.data == data:self.head = self.head.nextreturn# 遍历链表temp = self.headwhile temp.next is not None:if temp.next.data == data:breaktemp = temp.next# 删除节点if temp.next is not None:temp.next = temp.next.next
  

• 查询：查询链表中指定元素的位置

  # 节点类
  class Node:def __init__(self, data):self.data = dataself.next = None# 链表类
  class LinkedList:def __init__(self):self.head = None# 找到指定数据的位置def find_pos(self, data):# 如果链表为空if self.head is None:return -1# 遍历链表temp = self.headcount = 0while temp is not None:if temp.data == data:return counttemp = temp.nextcount += 1# 元素未找到return -1
  

• 修改：修改链表中指定元素的值

  
  # 节点类
  class Node:def __init__(self, data):self.data = dataself.next = None# 链表类
  class LinkedList:def __init__(self):self.head = None# 更新指定位置的节点def update_at_pos(self, pos, data):# 如果链表为空if self.head is None:return#遍历链表找到位置temp = self.headcount = 0while temp is not None:if count == pos:breaktemp = temp.nextcount += 1#更新节点if temp is not None:temp.data = data
  

• 遍历：从头到尾遍历整个链表

  # 节点类
  class Node:def __init__(self, data):self.data = dataself.next = None# 链表类
  class LinkedList:def __init__(self):self.head = None# 遍历链表def traverse(self):temp = self.headwhile temp is not None:print(temp.data)temp = temp.next
  

• 计数：计算链表中节点的数量

  # 节点类
  class Node:def __init__(self, data):self.data = dataself.next = None# 链表类
  class LinkedList:def __init__(self):self.head = None# 统计链表中节点的个数def count_nodes(self):temp = self.headcount = 0while temp is not None:count += 1temp = temp.nextreturn count
  

• 排序：对链表中的元素进行排序

  # 节点类
  class Node:def __init__(self, data):self.data = dataself.next = None# 链表类
  class LinkedList:def __init__(self):self.head = None# 对链表进行排序def sort_linked_list(self):temp = self.headwhile temp is not None:current = tempwhile current.next is not None:if current.data > current.next.data:current.data, current.next.data = current.next.data, current.datacurrent = current.nexttemp = temp.next
  

• 反转：将链表中的元素反转

  # 节点类
  class Node:def __init__(self, data):self.data = dataself.next = None# 链表类
  class LinkedList:def __init__(self):self.head = None# 反转链表def reverse(self):prev = Nonecurrent = self.headwhile current is not None:next = current.nextcurrent.next = prevprev = currentcurrent = nextself.head = prev
  

三、力扣上面一些有关链表的题目练习

1、移除链表元素

📖 给你一个链表的头节点 `head`和一个整数 `val`，请你删除链表中所有满足 `Node.val == val`的节点，并返回 **新的头节点。**

示例1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例2：

输入：head = [], val = 1
输出：[]

示例3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

---

🤔 这道题属于链表的基本操作，在上面介绍链表的常用方法时就提到了如何删除链表的元素，上面的方法是需要判断删除元素是否是链表头节点，也就是说删除头节点很删除其他节点的方法是不一样的，这是因为链表的其他节点都是通过前一格节点来移除当前节点，而头节点没有前一个节点，所以需要分开讨论，那么有没有一种统一的方法进行删除呢，当然，我们可以通过给原先链表设置一个虚拟头节点，这样原链表的所有节点就可以统一进行删除了。

那么什么是虚拟节点呢？

虚拟节点（dummy node）是在链表头部创建一个不存储任何数据的特殊节点，用来解决链表操作问题。通常情况下，在链表头部插入或移除元素时，需要特殊处理，以避免对链表头部的直接操作。使用虚拟节点，可以在链表头部插入和移除元素时统一处理，从而简化代码。

---

✍🏻 我们知道了要使用虚拟节点来进行链表的删除操作，具体的代码实现如下：

# Definition for singly-linked list.
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def removeElements(self, head: ListNode, val: int) -> ListNode:dummy = ListNode(0)dummy.next = headprev = dummycurrent = headwhile current:if current.val == val:prev.next = current.nextelse:prev = currentcurrent = current.nextreturn dummy.next

上述代码的具体实现思路如下：

1. 创建一个虚拟节点，该节点的值不重要，只是用来作为链表的头部。
2. 创建两个指针，一个指向虚拟节点（prev），一个指向链表头（current）。
3. 在链表中遍历每一个节点，如果该节点的值等于给定值val，则将prev的next指向该节点的下一个节点，即跳过该节点。如果该节点的值不等于给定值val，则将prev指向该节点。
4. 遍历完整个链表后，返回虚拟节点的next。

---

⚠️ 在解决上面题目时，我们应该注意以下几点：

1. 链表的遍历顺序：确保指针正确的遍历链表的每一个节点。
2. 变量的更新：确保在遍历每一个节点时，更新prev和current的值。
3. 虚拟节点的初始化：创建一个虚拟节点并且初始化它的next值为链表头。
4. 返回值：确保返回虚拟节点的next，而不是链表头。

如何要对上述代码进行示例测试的话，需要注意这跟之前的数组不一样，具体例子如下：

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(6)
head.next.next.next = ListNode(3)
head.next.next.next.next = ListNode(4)
head.next.next.next.next.next = ListNode(5)
head.next.next.next.next.next.next = ListNode(6)
a = Solution()
result = a.removeElements(head, 6)
node = result
while node:print(node.val, end=" ")node = node.next

B站上面卡尔老师对于这道题的思路讲得很不错，在这里推荐大家去看看他的教学视频：

https://www.bilibili.com/video/BV18B4y1s7R9/?spm_id_from=333.788&vd_source=eae0406d86828f39f6ac3a3b0e8a2a34

---

2、设计链表

📖 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
get, addAtHead, addAtTail, addAtIndex 和 deleteAtIndex 的操作次数不超过 2000。

---

🤔 这道题相当于将前面的基础知识进行整合考察我们对链表的操作，在这里我们方便起见还是继续使用虚拟头节点，这样可以对所有节点进行统一操作。

其中get(index)实现思路是：

1. 先判断给定的索引index是否合法，即是否小于0或大于链表的长度，如果不合法返回-1。
2. 定义一个当前节点cur，并将其设为头节点的下一个节点（即链表的第一个节点）。
3. 进入循环，当index不为0时，cur更新为其下一个节点，index减1。
4. 当循环结束后，cur的val属性即为所需要的值，返回该值。

其中addAtHead(val)实现思路是：

1. 创建新节点并设置其值。
2. 将新节点的next指针指向当前的链表头部。
3. 将新节点设为链表头部。
4. 更新链表的大小。

其中addAtTail(val)实现思路是：

1. 创建新节点并设置其值。
2. 创建当前指针，从链表头开始循环，直到找到链表的末尾。
3. 将新节点添加到末尾。
4. 更新链表的大小。

其中addAtIndex实现思路是：

1. 检查给定索引是否小于0或大于链表的大小，如果是，返回-1。
2. 创建新节点并设置其值。
3. 创建当前指针，从链表头开始循环，直到找到给定索引处的节点的前一个节点。
4. 将新节点的next指针指向给定索引处的节点。
5. 将前一个节点的next指针指向新节点。
6. 更新链表的大小。

其中deleteAtIndex(index)实现思路是：

1. 检查给定索引是否小于0或大于等于链表的大小，如果是，则返回。
2. 否则，创建一个当前指针，并从链表头开始循环，直到找到给定索引前一个节点。
3. 删除该节点并更新链表的大小。

---

✍🏻 上述是使用单链表实现的，具体实现代码如下：

class Node(object):def __init__(self, x=0):self.val = xself.next = Noneclass MyLinkedList(object):def __init__(self):self.head = Node()self.size = 0 # 设置一个链表长度的属性，便于后续操作，注意每次增和删的时候都要更新def get(self, index):""":type index: int:rtype: int"""if index < 0 or index >= self.size:return -1cur = self.head.nextwhile(index):cur = cur.nextindex -= 1return cur.valdef addAtHead(self, val):""":type val: int:rtype: None"""new_node = Node(val)new_node.next = self.head.nextself.head.next = new_nodeself.size += 1def addAtTail(self, val):""":type val: int:rtype: None"""new_node = Node(val)cur = self.headwhile(cur.next):cur = cur.nextcur.next = new_nodeself.size += 1def addAtIndex(self, index, val):""":type index: int:type val: int:rtype: None"""if index < 0:self.addAtHead(val)returnelif index == self.size:self.addAtTail(val)returnelif index > self.size:returnnode = Node(val)pre = self.headwhile(index):pre = pre.nextindex -= 1node.next = pre.nextpre.next = nodeself.size += 1def deleteAtIndex(self, index):""":type index: int:rtype: None"""if index < 0 or index >= self.size:returnpre = self.headwhile(index):pre = pre.nextindex -= 1pre.next = pre.next.nextself.size -= 1

---

👨🏻‍💻 这道题目我们还可以使用双向链表来实现，具体的实现过程连同代码我放在下面：

# 双链表
# 相对于单链表, Node新增了prev属性
class Node:def __init__(self, val):# 存储节点的值self.val = val# 指向前一个节点self.prev = None# 指向下一个节点self.next = None# 双链表的实现
class MyLinkedList:def __init__(self):# 虚拟节点，存储的值可以是0或者任意值self._head, self._tail = Node(0), Node(0)  # 虚拟节点的前一个节点和后一个节点都是自己self._head.next, self._tail.prev = self._tail, self._head# 添加的节点数self._count = 0  def _get_node(self, index: int) -> Node:# 当index小于_count//2时, 使用_head查找更快, 反之_tail更快if index >= self._count // 2:# 使用prev往前找node = self._tailfor _ in range(self._count - index):node = node.prevelse:# 使用next往后找node = self._head   for _ in range(index + 1):node = node.next# 返回找到的节点return nodedef get(self, index: int) -> int:"""获取链表中第 index 个节点的值。如果索引无效，则返回 -1。"""# 如果index是合法的，即在0和_count-1的范围内if 0 <= index < self._count:# 找到对应的节点node = self._get_node(index)# 返回该节点的值return node.valelse:# 如果index不合法，返回-1return -1def addAtHead(self, val: int) -> None:"""在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。"""# 调用_update方法，并传入链表的头节点，头节点的下一个节点，以及要插入的值valself._update(self._head, self._head.next, val)def addAtTail(self, val: int) -> None:"""将值为 val 的节点附加到链表的最后一个元素。"""# 调用_update方法，并传入链表的尾节点的前一个节点，尾节点，以及要插入的值valself._update(self._tail.prev, self._tail, val)def addAtIndex(self, index: int, val: int) -> None:"""在链表的第 index 个节点之前添加一个值为 val 的节点。如果索引等于链表的长度，则该节点将追加到链表的末尾。如果索引大于长度，则不会插入该节点。"""# 如果索引小于0，则将索引设置为0；如果索引大于链表长度，则直接返回if index < 0:index = 0elif index > self._count:return# 获取索引对应的节点node = self._get_node(index)# 调用_update方法，并传入该节点的前一个节点，该节点，以及要插入的值valself._update(node.prev, node, val)def _update(self, prev: Node, next: Node, val: int) -> None:"""更新节点:param prev: 相对于更新的前一个节点:param next: 相对于更新的后一个节点:param val:  要添加的节点值"""# 计数累加self._count += 1# 创建一个新节点node = Node(val)# 设置前后节点的指向prev.next, next.prev = node, nodenode.prev, node.next = prev, nextdef deleteAtIndex(self, index: int) -> None:"""如果索引有效，则删除链表中的第 index 个节点。"""# 如果 index 有效if 0 <= index < self._count:# 获取 index 节点node = self._get_node(index)# 计数-1self._count -= 1# 将前后节点的指向跳过该节点node.prev.next, node.next.prev = node.next, node.prev

B站上面卡尔老师对于这道题的思路讲得很不错，在这里推荐大家去看看他的教学视频：

https://www.bilibili.com/video/BV1FU4y1X7WD/?spm_id_from=333.788&vd_source=eae0406d86828f39f6ac3a3b0e8a2a34

---

3、反转链表

📖 给你单链表的头节点 `head`，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2:

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

---

🤔 这道反转链表的题目肯定不是让我们重新再定义一个新链表实现元素反转，其实我们反转链表只需要改变链表的next指针的指向，就可以直接将链表反转 ，而不用重新定义一个新的链表，具体实现的方法有两种：

1. 使用递归的方法，从链表的最后一个节点开始递归，每次递归都把当前节点的 next 指向前一个节点，最后返回新的头节点。
2. 使用循环的方法，通过循环，每次取出当前节点，并把当前节点的 next 指向前一个节点，最后把头节点指向最后一个节点。

递归的代码实现会非常的简洁，但是有时候会很难理解每一步的含义，所以我们可以先尝试使用第二种循环的方法，也就是使用双指针的方法反转链表。

---

✍🏻 用双指针实现的思路为：

1. 创建两个指针 pre 和 cur，pre 指向当前节点的前一个节点，cur 指向当前节点。
2. 使用 cur.next 来移动 cur，同时使用 pre 和 cur 实现反转。
3. 在每一轮循环中，cur 移动到下一个节点，pre 指向当前节点，cur.next 指向 pre。
4. 循环结束后，链表的头和尾已经反转。
5. 返回新的链表头，即原来的链表尾。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev

---

🏆 相比于双指针，递归的代码会更加简洁，下面是用递归的方法实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:# 终止条件：当前节点为空或当前节点的下一个节点为空if not head or not head.next:return head# 先递归到最后一个节点，让最后一个节点的下一个节点指向前一个节点new_head = self.reverseList(head.next)head.next.next = headhead.next = None# 返回新的头节点return new_head

我们还可以在原函数reverseList里面自己定义一个反转函数实现反转操作，具体实现过程如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: ListNode) -> ListNode:"""反转单链表:param head: 链表的头节点:return: 反轮后的链表头节点"""def reverse(pre, cur):"""递归函数，每次传入前一个节点和当前节点，反转链表:param pre: 前一个节点:param cur: 当前节点:return: 反转后的链表头节点"""if not cur:# 当前节点为空，说明已经到达末尾，返回前一个节点return pre# 保存当前节点的下一个节点tmp = cur.next# 反转链表，当前节点的下一个节点指向前一个节点cur.next = pre# 递归下一个节点return reverse(cur, tmp)# 从head开始，pre为Nonereturn reverse(None, head)

B站上面卡尔老师对于这道题的思路讲得很不错，在这里推荐大家去看看他的教学视频：

https://www.bilibili.com/video/BV1nB4y1i7eL/?spm_id_from=333.788&vd_source=eae0406d86828f39f6ac3a3b0e8a2a34

---

4、两两交换链表中的节点

📖 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例2：

输入：head = []
输出：[]

示例3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

---

🤔 这道题需要我们将链表中两两相邻的节点进行交换并返回最后交换后的链表，两两交换并不是简单的交换节点的值，而是需要改变实际的节点顺序。而且我们还需要考虑链表的节点数是奇数还是偶数的条件，所以循环迭代的终止条件是当循环迭代到链表为空或者链表只剩一个元素的时候停止迭代，实现的方法有两种方法：

• 递归实现：通过递归的方式对链表进行交换，并在递归过程中更新节点的指向。
• 迭代实现：通过迭代的方式对链表进行交换，通过不断更新节点的指向实现交换。

和上面的反转链表题目操作类似，我们还是先使用双指针迭代实现，然后再用递归的方法实现。

---

✍🏻 使用虚拟节点双指针迭代的方法实现：

1. 定义一个虚拟节点dummy，其next指向head。
2. 定义一个指针pre指向dummy，表示要交换的前一个节点。
3. 循环条件为pre的next指向的节点不为空且该节点的下一个节点也不为空。
4. 定义指针cur指向pre的next指向的节点，定义指针post指向cur的next指向的节点。
5. 交换cur和post两个节点：cur的next指向post的next指向的节点，post的next指向cur。
6. 将pre的next指向post。
7. 将pre指向pre的next指向的节点的next指向的节点。
8. 返回dummy的next指向的节点。

具体双指针代码实现如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def swapPairs(self, head: ListNode) -> ListNode:# 定义虚拟节点dummydummy = ListNode(0)dummy.next = headpre = dummywhile pre.next and pre.next.next:cur = pre.nextpost = cur.nextcur.next = post.nextpost.next = curpre.next = postpre = pre.next.nextreturn dummy.next

使用虚拟节点递归实现的思路：

1. 定义虚拟节点dummy，并将其next指向头节点。
2. 如果链表不为空，则从头节点开始递归，每次递归都会交换当前节点与其后面的节点。
3. 对于每次递归，通过将当前节点的next指向其后面的节点的next指针，并递归当前节点的next指针，实现链表节点的交换。
4. 递归边界为当前节点的next指针为None或只有一个节点时。
5. 完成递归后，返回头节点即可。

具体递归代码实现如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def swapPairs(self, head: ListNode) -> ListNode:# 定义虚拟节点dummydummy = ListNode(0)dummy.next = headif head and head.next:next_node = head.next.nexthead.next.next = headhead.next = self.swapPairs(next_node)dummy.next = head.nextreturn dummy.next

如果使用动态状态方程写的话可以更加简洁：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def swapPairs(self, head: ListNode) -> ListNode:# 定义虚拟节点dummydummy = ListNode(0)dummy.next = headif head and head.next:head.next, dummy.next.next, dummy.next = self.swapPairs(head.next.next), head, head.nextreturn dummy.next

B站上面卡尔老师对于这道题的思路讲得很不错，在这里推荐大家去看看他的教学视频：

https://www.bilibili.com/video/BV1YT411g7br/?spm_id_from=333.788&vd_source=eae0406d86828f39f6ac3a3b0e8a2a34

---

5、删除链表的倒数第N个节点

📖 给你一个链表，删除链表的倒数第 `n` **个结点，并且返回链表的头结点。

示例1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例2：

输入：head = [1], n = 1
输出：[]

示例3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

---

🤔 删除链表的第n个节点跟我们之前练习数组的题目移除元素类似，我们可以使用快慢指针的方法来实现它。如果要删除倒数第n个节点，我们可以让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾，最后删掉slow所指向的节点就可以了。同样的我们继续使用虚拟头节点来解决这个问题。

---

✍🏻 快慢指针法的思路如下：

1. 定义虚拟节点dummy，把dummy的next指向head，并定义快指针fast和慢指针slow，都指向dummy。
2. 先将快指针移动n+1步，使其到达链表的结尾或倒数第n个位置。
3. 然后同时移动快指针和慢指针，直到快指针到达链表的末尾。
4. 最后把慢指针的下一个节点删除。
5. 返回dummy的next，作为新的链表的头结点。

具体代码实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy = ListNode(0)dummy.next = headslow = dummyfast = dummyfor i in range(n + 1):fast = fast.nextwhile fast:slow = slow.nextfast = fast.nextslow.next = slow.next.nextreturn dummy.next

我们还可以换一种写法来实现：

首先，我们新增一个虚拟节点 dummy，它的下一个节点是原链表的头节点 head。然后，我们定义两个指针 slow 和 fast，它们都从 dummy 出发，最开始 fast 指针先往前走 n 步。接着，两个指针同时向前走，当 fast 指针到达结尾后，slow 的下一个节点就是倒数第 N 个节点。最后，我们直接删除该节点，然后返回 dummy.next 即可。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy = ListNode()dummy.next = headslow, fast = dummy, dummywhile(n!=0): #fast先往前走n步fast = fast.nextn -= 1while(fast.next!=None):slow = slow.nextfast = fast.next#fast 走到结尾后，slow的下一个节点为倒数第N个节点slow.next = slow.next.next #删除return dummy.next

B站上面卡尔老师对于这道题的思路讲得很不错，在这里推荐大家去看看他的教学视频：

https://www.bilibili.com/video/BV1vW4y1U7Gf/?spm_id_from=333.788

---

6、相交链表

📖 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SzDLGQGH-1676269812178)(https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png)]

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n)、仅用 O(1)内存的解决方案？

---

🤔 这道题有A,B两个方向需要遍历，所以我们可以让两个指针同时从两个链表的头节点开始走，直到两个指针相遇，或者其中一个指针遍历完了自己的链表，此时再将该指针指向另一个链表的头节点，并继续遍历，直到两个指针相遇，此时相遇的节点即为第一个公共节点。

---

✍🏻 具体实现的思路是：

1. 创建两个指针pA和pB，分别指向两个链表的头结点headA和headB。

2. 先判断两个链表是否存在交点：

   a. 如果pA == pB，则返回pA，说明此时两个指针所指向的结点就是交点。

   b. 如果pA != pB，则继续遍历：

   i. 若pA存在，则将pA移动到pA.next，否则将pA指向headB；

   ii. 若pB存在，则将pB移动到pB.next，否则将pB指向headA。

3. 循环2的步骤，直到pA == pB或pA和pB均不存在，此时说明两个链表没有交点或已经找到了交点。

知道了具体实现思路，那么写出代码也就不是很难了，具体代码实现是：

# Definition for singly-linked list.
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:pA = headApB = headBwhile pA != pB:pA = pA.next if pA else headBpB = pB.next if pB else headAreturn pA

我们使用的这种方法的优点在于，不论两个链表的长度是否相等，最多只需要遍历两次链表，时间复杂度为O(m + n)，其中m和n分别是两个链表的长度。

---

7、环形链表Ⅱ

📖 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1)空间解决此题？

---

🤔 当我们看到这个题目的时候，我们首先要了解题目的意思，简单的来说就是给定一个链表，判断是否存在环，如果存在环，则找到环的入口。知道题目的意思之后，我们就知道题目的重点在于用什么方法判断是否存在环以及如何找到环的入口，我们可以联想到我们之前经常用到的方法，那就是快慢指针的方法，实现方法大概就是用两个指针fast和slow，分别指向head，每次将fast移动到fast.next.next，将slow移动到slow.next，也就是快指针移动的速度是满指针的两倍，如果fast == slow，则说明存在环。解决完判断是否存在环的问题之后，我们还要思考如何找到环的入口，我们可以将slow指向head，同时保持fast不变，再次每次将slow移动到slow.next，将fast移动到fast.next，如果在某一时刻slow == fast，则说明slow和fast所指向的结点即为环的入口。

---

✍🏻 知道了解决思路之后我们就可以写出代码了。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: ListNode) -> ListNode:fast = slow = headwhile fast and fast.next:fast = fast.next.nextslow = slow.nextif fast == slow:slow = headwhile slow != fast:slow = slow.nextfast = fast.nextreturn slowreturn None

上述算法的实现步骤为：

1. 创建两个指针fast和slow，分别指向head。
2. 每次将fast移动到fast.next.next，将slow移动到slow.next。
3. 如果fast == slow，说明链表存在环。此时，将slow指向head，同时保持fast不变，再次每次将slow移动到slow.next，将fast移动到fast.next。如果在某一时刻slow == fast，则说明slow和fast所指向的结点即为环的入口。
4. 如果fast不存在或fast.next不存在，则说明链表不存在环，返回None。

B站上面卡尔老师对于这道题的思路讲得很不错，在这里推荐大家去看看他的教学视频：

https://www.bilibili.com/video/BV1if4y1d7ob/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=eae0406d86828f39f6ac3a3b0e8a2a34