全部题目来自力扣，这里只做学习的记录，内容中部分为AI生成，有不对的地方可以评论或者私信哦~~
203. 移除链表元素
（版本一）虚拟头节点法
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:# 创建虚拟头部节点以简化删除过程dummy_head = ListNode(next = head)# 遍历列表并删除值为val的节点current = dummy_headwhile current.next:if current.next.val == val:current.next = current.next.nextelse:current = current.nextreturn dummy_head.next707. 设计链表
（版本一）单链表法
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList:def __init__(self):self.dummy_head = ListNode()self.size = 0def get(self, index: int) -> int:if index < 0 or index >= self.size:return -1current = self.dummy_head.nextfor i in range(index):current = current.nextreturn current.valdef addAtHead(self, val: int) -> None:self.dummy_head.next = ListNode(val, self.dummy_head.next)self.size += 1def addAtTail(self, val: int) -> None:current = self.dummy_headwhile current.next:current = current.nextcurrent.next = ListNode(val)self.size += 1def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.size:returncurrent = self.dummy_headfor i in range(index):current = current.nextcurrent.next = ListNode(val, current.next)self.size += 1def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.size:returncurrent = self.dummy_headfor i in range(index):current = current.nextcurrent.next = current.next.nextself.size -= 1# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)（版本二）双链表法
class ListNode:def __init__(self, val=0, prev=None, next=None):self.val = valself.prev = prevself.next = nextclass MyLinkedList:def __init__(self):self.head = Noneself.tail = Noneself.size = 0def get(self, index: int) -> int:if index < 0 or index >= self.size:return -1if index < self.size // 2:current = self.headfor i in range(index):current = current.nextelse:current = self.tailfor i in range(self.size - index - 1):current = current.prevreturn current.valdef addAtHead(self, val: int) -> None:new_node = ListNode(val, None, self.head)if self.head:self.head.prev = new_nodeelse:self.tail = new_nodeself.head = new_nodeself.size += 1def addAtTail(self, val: int) -> None:new_node = ListNode(val, self.tail, None)if self.tail:self.tail.next = new_nodeelse:self.head = new_nodeself.tail = new_nodeself.size += 1def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.size:returnif index == 0:self.addAtHead(val)elif index == self.size:self.addAtTail(val)else:if index < self.size // 2:current = self.headfor i in range(index - 1):current = current.nextelse:current = self.tailfor i in range(self.size - index):current = current.prevnew_node = ListNode(val, current, current.next)current.next.prev = new_nodecurrent.next = new_nodeself.size += 1def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.size:returnif index == 0:self.head = self.head.nextif self.head:self.head.prev = Noneelse:self.tail = Noneelif index == self.size - 1:self.tail = self.tail.previf self.tail:self.tail.next = Noneelse:self.head = Noneelse:if index < self.size // 2:current = self.headfor i in range(index):current = current.nextelse:current = self.tailfor i in range(self.size - index - 1):current = current.prevcurrent.prev.next = current.nextcurrent.next.prev = current.prevself.size -= 1# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)206. 反转链表
#（版本一）双指针法
class Solution:def reverseList(self, head: ListNode) -> ListNode:cur = head pre = Nonewhile cur:temp = cur.next # 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur.next = pre #反转#更新pre、cur指针pre = curcur = tempreturn pre#（版本二）递归法
class Solution:def reverseList(self, head: ListNode) -> ListNode:return self.reverse(head, None)def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:if cur == None:return pretemp = cur.nextcur.next = prereturn self.reverse(temp, cur)234. 回文链表
算法思路
-
核心思想：
- 找到链表的中间节点。
- 反转链表的后半部分。
- 比较链表的前半部分和反转后的后半部分，如果值完全一致，则是回文链表。
-
具体步骤：
- 使用快慢指针找到链表的中间节点（
middleNode方法）。 - 反转链表的后半部分（
reverseList方法）。 - 比较链表的前半部分和反转后的后半部分，如果所有节点的值都相等，则返回
True，否则返回False。
- 使用快慢指针找到链表的中间节点（
-
关键点：
- 快慢指针找到中间节点的时间复杂度为
O(n)。 - 反转链表的时间复杂度为
O(n)。 - 比较链表的时间复杂度为
O(n)。 - 总时间复杂度为
O(n)，空间复杂度为O(1)
- 快慢指针找到中间节点的时间复杂度为
class ListNode:def __init__(self, x):self.val = x # 初始化节点的值self.next = None # 初始化节点的下一个节点为 Noneclass Solution:# 876. 链表的中间结点def middleNode(self, head):slow = fast = head # 初始化慢指针和快指针，都指向链表头节点while fast and fast.next: # 当快指针及其下一个节点不为空时slow = slow.next # 慢指针每次移动一步fast = fast.next.next # 快指针每次移动两步return slow # 返回慢指针指向的节点（即链表的中间节点）# 206. 反转链表def reverseList(self, head):pre, cur = None, head # 初始化前驱节点为 None，当前节点为链表头节点while cur: # 当当前节点不为空时nxt = cur.next # 保存当前节点的下一个节点cur.next = pre # 将当前节点的 next 指向前驱节点pre = cur # 前驱节点移动到当前节点cur = nxt # 当前节点移动到下一个节点return pre # 返回反转后的链表头节点def isPalindrome(self, head):mid = self.middleNode(head) # 找到链表的中间节点head2 = self.reverseList(mid) # 反转后半部分链表while head2: # 遍历反转后的后半部分链表if head.val != head2.val: # 如果前半部分和后半部分的节点值不相等return False # 不是回文链表，返回 Falsehead = head.next # 移动前半部分的指针head2 = head2.next # 移动后半部分的指针return True # 所有节点值都相等，是回文链表，返回 True24. 两两交换链表中的节点
# 递归版本class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if head is None or head.next is None:return head# 待翻转的两个node分别是pre和curpre = headcur = head.nextnext = head.next.nextcur.next = pre # 交换pre.next = self.swapPairs(next) # 将以next为head的后续链表两两交换return cur
代码执行示例
假设链表为：1 -> 2 -> 3 -> 4 -> None
执行过程：
- 第一次递归调用：
pre = 1，cur = 2，next = 3- 交换
pre和cur：2 -> 1 - 递归处理
next = 3，得到交换后的链表4 -> 3 - 将
pre.next（即1.next）指向4 -> 3，最终链表为2 -> 1 -> 4 -> 3 -> None - 返回
cur = 2，即交换后的新链表头节点。
最终链表为：2 -> 1 -> 4 -> 3 -> None
# Definition for singly-linked list.class Solution:def swapPairs(self, head: ListNode) -> ListNode:dummy_head = ListNode(next=head)current = dummy_head# 必须有cur的下一个和下下个才能交换，否则说明已经交换结束了while current.next and current.next.next:temp = current.next # 防止节点修改temp1 = current.next.next.nextcurrent.next = current.next.nextcurrent.next.next = temptemp.next = temp1current = current.next.nextreturn dummy_head.next19. 删除链表的倒数第 N 个结点
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:# 创建一个虚拟节点，并将其下一个指针设置为链表的头部dummy_head = ListNode(0, head)# 创建两个指针，慢指针和快指针，并将它们初始化为虚拟节点slow = fast = dummy_head# 快指针比慢指针快 n+1 步for i in range(n+1):fast = fast.next# 移动两个指针，直到快速指针到达链表的末尾while fast:slow = slow.nextfast = fast.next# 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点slow.next = slow.next.nextreturn dummy_head.next
141. 环形链表
方法一
-
核心思想：
- 使用一个集合
seen来记录已经访问过的节点。 - 遍历链表，如果当前节点已经存在于集合中，说明链表存在环；否则，将当前节点添加到集合中，继续遍历。
- 如果遍历结束（
head为None），说明链表没有环。
- 使用一个集合
-
时间复杂度：
- 最坏情况下需要遍历整个链表，时间复杂度为
O(n)，其中n是链表的节点数。
- 最坏情况下需要遍历整个链表，时间复杂度为
-
空间复杂度：
- 使用了一个集合
seen来存储节点，空间复杂度为O(n)。
- 使用了一个集合
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution(object):def hasCycle(self, head):""":type head: ListNode:rtype: bool"""seen = set()while head:if head in seen:return Trueseen.add(head)head = head.nextreturn False方法二
-
快慢指针的核心思想：
- 快指针每次移动两步，慢指针每次移动一步。
- 如果链表存在环，快指针最终会追上慢指针（相遇）。
- 如果链表不存在环，快指针会先到达链表末尾。
-
时间复杂度：
O(n)。 -
空间复杂度：
O(1)。
def hasCycle(self, head):slow = fast = head # 初始化慢指针和快指针，都指向链表头节点while fast and fast.next: # 当快指针及其下一个节点不为空时slow = slow.next # 慢指针每次移动一步fast = fast.next.next # 快指针每次移动两步if slow == fast: # 如果快慢指针相遇return True # 说明链表存在环return False # 遍历结束，没有发现环142. 环形链表 II
快慢指针法
-
核心思想：
- 快慢指针：
- 使用快慢指针（
fast和slow）遍历链表。 - 快指针每次移动两步，慢指针每次移动一步。
- 如果链表存在环，快指针最终会追上慢指针（相遇）。
- 使用快慢指针（
- 找到环的入口：
- 当快慢指针相遇时，初始化一个新指针
ptr，指向链表头节点。 - 同时移动
ptr和slow，每次移动一步，直到它们相遇。 - 相遇的节点就是环的入口节点。
- 当快慢指针相遇时，初始化一个新指针
- 快慢指针：
-
时间复杂度：
- 最坏情况下需要遍历整个链表，时间复杂度为
O(n)，其中n是链表的节点数。
- 最坏情况下需要遍历整个链表，时间复杂度为
-
空间复杂度：
- 只使用了常数级别的额外空间，空间复杂度为
O(1)。
- 只使用了常数级别的额外空间，空间复杂度为
class Solution:def detectCycle(self, head):slow = fast = head # 初始化慢指针和快指针，都指向链表头节点while fast is not None: # 当快指针不为空时slow = slow.next # 慢指针每次移动一步if fast.next is None: # 如果快指针的下一个节点为空return None # 说明链表没有环，返回 Nonefast = fast.next.next # 快指针每次移动两步if fast == slow: # 如果快慢指针相遇ptr = head # 初始化一个新指针，指向链表头节点while ptr != slow: # 当新指针和慢指针不相遇时ptr = ptr.next # 新指针每次移动一步slow = slow.next # 慢指针每次移动一步return ptr # 返回新指针指向的节点（即环的入口节点）return None # 遍历结束，没有发现环，返回 None21. 合并两个有序链表
1. 算法思路
这段代码的核心思想是 合并两个有序链表。具体步骤如下：
-
初始化哨兵节点：
- 创建一个哨兵节点
dummy，用于简化链表操作，避免处理头节点的特殊情况。 - 使用指针
cur指向dummy，用于构建新的链表。
- 创建一个哨兵节点
-
遍历两个链表：
- 使用
while l1 and l2循环遍历两个链表，比较当前节点的值：- 如果
l1.val < l2.val，将l1节点连接到cur的后面，并移动l1指针。 - 否则，将
l2节点连接到cur的后面，并移动l2指针。
- 如果
- 每次连接一个节点后，移动
cur指针到新连接的节点。
- 使用
-
处理剩余部分：
- 当其中一个链表遍历完毕后，将另一个链表的剩余部分直接连接到
cur的后面。
- 当其中一个链表遍历完毕后，将另一个链表的剩余部分直接连接到
-
返回结果：
- 返回
dummy.next，即合并后的链表的头节点。
- 返回
2. 时间复杂度
- 最坏情况：
- 需要遍历两个链表的全部节点，假设两个链表的长度分别为
m和n，则时间复杂度为 O(m + n)。
- 需要遍历两个链表的全部节点，假设两个链表的长度分别为
- 最好情况：
- 如果其中一个链表为空，直接返回另一个链表，时间复杂度为 O(1)。
3. 空间复杂度
- 额外空间：
- 只使用了常数级别的额外空间（哨兵节点
dummy和指针cur），因此空间复杂度为 O(1)。
- 只使用了常数级别的额外空间（哨兵节点
- 原地修改：
- 代码直接修改了输入的链表，没有创建新的链表节点，因此空间复杂度较低。
class Solution:def mergeTwoLists(self, l1, l2):dummy = ListNode(0) # 哨兵节点cur = dummywhile l1 and l2:if l1.val < l2.val:cur.next = l1l1 = l1.nextelse:cur.next = l2l2 = l2.nextcur = cur.nextcur.next = l1 if l1 else l2 # 将剩余部分连接到结果链表return dummy.next
