力扣hot100_链表(3)_python版本-平芜编程栈

以下是力扣（LeetCode）Hot 100链表专题的Python实现，涵盖常见题型及解法。内容按题目分类整理，避免步骤词汇，直接提供解题思路和代码示例。

反转链表

经典问题，迭代或递归实现链表的反转。

迭代法

def reverseList(head): prev, curr = None, head while curr: next_temp = curr.next curr.next = prev prev = curr curr = next_temp return prev

递归法

def reverseList(head): if not head or not head.next: return head p = reverseList(head.next) head.next.next = head head.next = None return p

合并两个有序链表

双指针遍历，比较节点值后合并。

def mergeTwoLists(l1, l2): dummy = ListNode(-1) curr = dummy while l1 and l2: if l1.val <= l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next curr.next = l1 if l1 else l2 return dummy.next

https://www.zhihu.com/zvideo/1994540824894140691/
https://www.zhihu.com/zvideo/1994540825489711113/
https://www.zhihu.com/zvideo/1994540824344678795/
https://www.zhihu.com/zvideo/1994540822813751101/
https://www.zhihu.com/zvideo/1994540822474019451/
https://www.zhihu.com/zvideo/1994540821597423591/
https://www.zhihu.com/zvideo/1994540819441545962/
https://www.zhihu.com/zvideo/1994540807810748692/
https://www.zhihu.com/zvideo/1994540808007872957/
https://www.zhihu.com/zvideo/1994540806548254902/
https://www.zhihu.com/zvideo/1994540806317565460/
https://www.zhihu.com/zvideo/1994540805520634546/
https://www.zhihu.com/zvideo/1994540803159249475/
https://www.zhihu.com/zvideo/1994540802739815780/
https://www.zhihu.com/zvideo/1994540802915972236/
https://www.zhihu.com/zvideo/1994540791222247715/
https://www.zhihu.com/zvideo/1994540790983185579/
https://www.zhihu.com/zvideo/1994540790349844503/
https://www.zhihu.com/zvideo/1994540789573887713/
https://www.zhihu.com/zvideo/1994540789531955706/
https://www.zhihu.com/zvideo/1994540787095065282/
https://www.zhihu.com/zvideo/1994540786340078183/

链表中倒数第k个节点

快慢指针法，快指针先走k步，再同步移动。

def getKthFromEnd(head, k): fast = slow = head for _ in range(k): fast = fast.next while fast: fast = fast.next slow = slow.next return slow

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

结合虚拟头节点和快慢指针，避免边界问题。

def removeNthFromEnd(head, n): dummy = ListNode(0, head) fast = slow = dummy for _ in range(n + 1): fast = fast.next while fast: fast = fast.next slow = slow.next slow.next = slow.next.next return dummy.next

相交链表

双指针遍历两链表，到达末尾时切换头节点，相遇点为交点。

def getIntersectionNode(headA, headB): pA, pB = headA, headB while pA != pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA

环形链表

快慢指针判断是否存在环，相遇即有环。

def hasCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False

环形链表 II

快慢指针相遇后，重置慢指针到头部，同步移动至再次相遇。

def detectCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: slow = head while slow != fast: slow = slow.next fast = fast.next return slow return None

回文链表

反转后半部分链表后与前半部分比较。

def isPalindrome(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next prev = None while slow: next_temp = slow.next slow.next = prev prev = slow slow = next_temp left, right = head, prev while right: if left.val != right.val: return False left = left.next right = right.next return True

两数相加

模拟加法运算，注意进位处理。

def addTwoNumbers(l1, l2): dummy = curr = ListNode(0) carry = 0 while l1 or l2 or carry: v1 = l1.val if l1 else 0 v2 = l2.val if l2 else 0 sum_val = v1 + v2 + carry carry = sum_val // 10 curr.next = ListNode(sum_val % 10) curr = curr.next l1 = l1.next if l1 else None l2 = l2.next if l2 else None return dummy.next

LRU缓存

双向链表+哈希表实现O(1)时间复杂度的get和put。

class DLinkedNode: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity): self.cache = {} self.capacity = capacity self.head = DLinkedNode() self.tail = DLinkedNode() self.head.next = self.tail self.tail.prev = self.head def get(self, key): if key not in self.cache: return -1 node = self.cache[key] self._move_to_head(node) return node.value def put(self, key, value): if key in self.cache: node = self.cache[key] node.value = value self._move_to_head(node) else: node = DLinkedNode(key, value) self.cache[key] = node self._add_node(node) if len(self.cache) > self.capacity: removed = self._pop_tail() del self.cache[removed.key] def _add_node(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove_node(self, node): prev = node.prev next_node = node.next prev.next = next_node next_node.prev = prev def _move_to_head(self, node): self._remove_node(node) self._add_node(node) def _pop_tail(self): node = self.tail.prev self._remove_node(node) return node