第一题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 100l1和l2均按非递减顺序排列思路新建一个虚拟节点用这个虚拟节点的next作为向后更新的节点。每次的具体操作是先判断两个链表是否存在若其中的一个链表到头了那就直接在结尾连接上另一个存在的链表即可。而若是两个链表均存在就需要判断其中的数值连接上数值小的一方然后向后移动直至两个链表其中一个走到头了。代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # 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, val0, nextNone): # 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]提示链表中节点数目为n1 n 500-500 Node.val 5001 left right n思路先定位到left左边一个位置然后再进行for循环right - left次操作。每次反转的原理是将nextnode插入到pre之后。重点就是这三行代码要好好理解。移示例1[1,2,3,4,5]为例left 2right 4首先定位到pre在1这个结点那么cur就是2cur这个结点是不会变的此时的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, val0, nextNone): # 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): # 先暂存nextnodecur的后一个 nextnode cur.next # 这三行代码是反转链表的核心代码作用是将nextnode插到pre的后面一个 # 以示例1为例子此时nextnode是3这个结点上一步被暂存了 # 现在将2后面的箭头指向4nextnode.next cur.next nextnode.next # 然后将3后面的箭头2原本pre后面的箭头 nextnode.next pre.next # 将pre后面的箭头指向3 pre.next nextnode return dummy.next