力扣算法面试150题——链表——个人笔记

第一题

141. 环形链表https://leetcode.cn/problems/linked-list-cycle/

题目内容

给你一个链表的头节点head，判断链表中是否有环。

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

如果链表中存在环，则返回true。 否则，返回false。

示例 1：

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

示例 2：

示例 2： 输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

示例 3： 输入：head = [1], pos = -1 输出：false 解释：链表中没有环。

思路

两种思路：哈希表 or 快慢指针。

哈希表：

用一个集合来存储当前结点，若某一结点存在于集合中，则说明有环，返回True，否则就将该结点添加进集合当中，直到链表结束都没有重复的话，就说明是无环，返回False。

快慢指针：

两根指针指向开头，一根每次走一步，另一根每次走两步，若两个指针能相遇，则说明有环，否则无环。只要快慢指针不相等，就持续while循环，除非快指针或者快指针的next不存在了（因为快指针一次走两步），则说明真的走到头了，不会有环了。

代码

# 哈希表 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: arrive = set() cur = head while cur: if cur in arrive: return True arrive.add(cur) cur = cur.next return False

# 快慢双指针 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: if not head or not head.next: return False slow = head fast = head.next while slow != fast: if not (fast and fast.next): return False slow = slow.next fast = fast.next.next return True

第二题

21. 合并两个有序链表https://leetcode.cn/problems/merge-two-sorted-lists/

题目内容

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

示例 1：

示例 1： ​​​​​​​输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 示例 2： 输入：l1 = [], l2 = [] 输出：[] 示例 3： 输入：l1 = [], l2 = [0] 输出：[0]

提示：

• 两个链表的节点数目范围是[0, 50]
• -100 <= Node.val <= 100
• l1和l2均按非递减顺序排列

思路

新建一个虚拟节点，用这个虚拟节点的next作为向后更新的节点。每次的具体操作是：

先判断两个链表是否存在，若其中的一个链表到头了，那就直接在结尾连接上另一个存在的链表即可。而若是两个链表均存在，就需要判断其中的数值，连接上数值小的一方，然后向后移动，直至两个链表其中一个走到头了。

代码

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: # 构建一个虚拟头 dummy = ListNode() # 用cur表示当前位置，开始时cur就是dummy，但是随着后续的操作，cur会移动到链表尾部 cur = dummy # 只要两个链表都不为空，就一直while循环 while list1 and list2: val1 = list1.val if list1 else 0 val2 = list2.val if list2 else 0 # 将cur.next 连接较小的那个结点， if val1 < val2: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next # cur 自己向后移动 cur = cur.next # 这个时候说明两个链表中至少有一个为空了，那就直接在现有的基础上连接另外一个即可（这里写的有点冗余，但是可读性更高） if list1: cur.next = list1 cur = cur.next if list2: cur.next = list2 cur = cur.next # 返回虚拟头的下一个结点，相当于从头开始直至cur结束 return dummy.next

第三题

2. 两数相加https://leetcode.cn/problems/add-two-numbers/

题目内容

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

示例 1： 输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807. 示例 2： 输入：l1 = [0], l2 = [0] 输出：[0] 示例 3： 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围[1, 100]内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

思路

这里需要构建新表，因此依旧可以利用虚拟表头的方式，以及在while循环中构建新的结点。

首先观察到两个链表长度可以不一样，因此还是分类讨论，当两个链表其中一方是None的时候，两个链表该如何移动？此外还要注意有一个进位符，例如999和1，就变成1000了，需要进一位，因此我们可以推得循环条件，当：表1存在 或 表2存在 或进位符存在 的时候，进入while 循环。

在循环内，首先处理获得进位符和当前结点的val，然后用该数值构建新节点，cur移到当前结点。

最后l1和l2其中有一方可能会为空，因此在next往后移动之前需要if判断条件

代码

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() cur = dummy cnt = 0 # 只有可能是0或1 # 当表1不为空 or 表2不为空 or 进位符为1的时候，进入while循环 while l1 or l2 or cnt: # 处理当前总值 val1 = l1.val if l1 else 0 val2 = l2.val if l2 else 0 total = val1 + val2 + cnt # 更新进位符 cnt = total // 10 # 用更新后的数值创建新结点，并移动至此 finalval = total % 10 cur.next = ListNode(finalval) cur = cur.next # l1和l2向后挪动之前先判断到头了没 l1 = l1.next if l1 else None l2 = l2.next if l2 else None return dummy.next

第四题

92.反转链表 IIhttps://leetcode.cn/problems/reverse-linked-list-ii/

题目内容

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

示例 1：

示例1： 输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5] 示例 2： 输入：head = [5], left = 1, right = 1 输出：[5]

提示：

• 链表中节点数目为n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

思路

先定位到left左边一个位置，然后再进行for循环（right - left）次操作。每次反转的原理是将nextnode插入到pre之后。重点就是这三行代码，要好好理解。移示例1：[1,2,3,4,5]为例，left = 2，right = 4

首先定位到pre在1这个结点，那么cur就是2（cur这个结点是不会变的），此时的nextnode 是3这个结点。将3移除，并放在pre之后，于是整个链表变成了[1,3,2,4,5]，这是第一次循环结束后的样子。

然后进入第二轮，此时的nextnode变成了4（因为此时链表是[1,3,2,4,5]，cur是2这个结点不变，nextnode每次都会变），于是将4插入到pre后面，链表变成了[1,4,3,2,5]，也就是最终的目标。完成！

代码

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: dummy = ListNode() dummy.next = head pre = dummy # 先定位到left前一个，记作pre for _ in range(left - 1): pre = pre.next # 此时的cur就是left，不管后续如何操作，这个cur是固定不会变的 cur = pre.next for _ in range(right - left): # 先暂存nextnode（cur的后一个） nextnode = cur.next # 这三行代码是反转链表的核心代码，作用是将nextnode插到pre的后面一个 # 以示例1为例子，此时nextnode是3这个结点，上一步被暂存了 # 现在将2后面的箭头指向4（nextnode.next） cur.next = nextnode.next # 然后将3后面的箭头2（原本pre后面的箭头） nextnode.next = pre.next # 将pre后面的箭头指向3 pre.next = nextnode return dummy.next