链表：一种简单但强大的数据结构
链表：一种简单但强大的数据结构
Jessica Gracewell开篇：
链表，作为计算机科学中的基础数据结构之一，以其独特的存储方式和灵活的操作性质，在众多应用场景中占据着不可或缺的地位。它并不像数组那样需要连续的内存空间，因此在内存的利用上更加灵活和高效。不论是在操作系统的内存管理，还是在各类高级算法和数据结构的实现中，链表都发挥着重要的作用。对链表的深入理解和熟练应用，是每个学习计算机科学和软件工程的人必须掌握的基本技能。
本博客旨在提供一份全方位、多层次、深入浅出的链表学习材料。我们将从链表的基础概念出发，逐步深入到链表的高级操作和应用，涵盖了链表的方方面面。无论你是计算机科学的新学者，还是有一定基础但希望更进一步的学习者，甚至是寻求更多应用实例和优化策略的资深开发者，都能在这里找到所需的知识和灵感。
通过本博客，你将系统地学习到链表的基础知识、核心概念、基本操作、高级技巧、优化策略以及实际应用。实际代码将帮助你更加具体和深入地理解链表的实现和应用。希望通过这份博客，你能够更加清晰、更加深刻地理解链表，将这一基础但极其重要的数据结构运用自如。
第一部分：链表基础与核心概念
链表是一种常用的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表经常被用于实现其他高级数据结构，如栈和队列。
1. 基础概念与核心点
- null/nil异常处理：处理空指针是链表操作中的常见任务，忽略这一点可能导致程序崩溃。
- dummy node（哑巴节点）：当链表头部可能发生变化时，哑巴节点能帮助我们更容易地处理链表，而不用担心链表的头部丢失。
- 快慢指针：快慢指针技巧是解决链表问题的另一个常用方法，例如，寻找链表的中点
2. 常见链表操作
- 插入一个节点到排序链表
- 从一个链表中移除一个节点
- 翻转链表
- 合并两个链表
- 找到链表的中间节点
3. 常见问题
1. 删除所有重复的元素
def delete_duplicates(head): |
2. 删除所有含有重复数字的节点
def delete_all_duplicates(head): |
3. 反转一个单链表
def reverse_list(head): |
4. 注意点
- 在删除节点时，例如从 A->B->C 中删除 B，应该设置 A.next = C。
- 在访问 X.next 或 X.value 时，一定要确保 X != nil，以避免 null/nil 异常
第二部分：链表的深入理解与高级操作
1. 反转链表的一部分
如果我们想要反转链表的一部分，我们需要做一些额外的工作来确保链表的其余部分保持不变。我们需要定位到要反转的部分，然后反转它，最后再将其重新连接到链表中。def reverse_between(head, m, n):
if not head: return head
dummy = ListNode(0) # 使用哑巴节点以处理头部可能会变化的情况
dummy.next = head
head = dummy
pre = None
for _ in range(m):
pre = head
head = head.next
next_node = None
first_part_last_node = pre
rev_part_last_node = head
for _ in range(n - m + 1):
temp = head.next
head.next = next_node
next_node = head
head = temp
first_part_last_node.next = next_node
rev_part_last_node.next = head
return dummy.next2. 链表排序
链表排序是另一个重要但复杂的问题。归并排序是解决这个问题的一种有效方法，因为它具有 O(n log n) 的时间复杂度和常数级的空间复杂度。def sort_list(head):
def find_middle(node):
slow, fast = node, node.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def merge(l1, l2):
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
if not head or not head.next: return head
middle = find_middle(head)
right = sort_list(middle.next)
middle.next = None
left = sort_list(head)
return merge(left, right)3. 判断链表是否有环
判断链表是否有环是一个经典的问题。我们可以使用快慢指针来解决这个问题。如果快慢指针在某个时刻相遇，那么链表就有环。def has_cycle(head):
if not head: return False
slow, fast = head, head.next
while fast and fast.next:
if slow == fast: return True
slow = slow.next
fast = fast.next.next
return False4. 找到链表环的起点
如果链表中存在环，我们还可以找到环的起点。当快慢指针相遇时，我们将一个指针移回到链表的起点，然后以相同的速度移动两个指针，当它们再次相遇时，相遇点就是环的起点。def detect_cycle(head):
if not head: return None
slow, fast = head, head.next
while fast and fast.next:
if slow == fast:
fast = head
while slow.next != fast:
slow = slow.next
fast = fast.next
return slow.next
slow = slow.next
fast = fast.next.next
return None
第三部分：链表问题的解决策略
1. 回文链表
判断一个链表是否是回文链表是一个常见的问题。我们可以利用快慢指针找到中点，然后反转后半部分，最后比较前后两部分是否相等。def is_palindrome(head):
if not head: return True
def reverse(node):
prev = None
while node:
temp = node.next
node.next = prev
prev = node
node = temp
return prev
# 找到中点
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 反转后半部分链表
tail = reverse(slow)
while tail:
if head.val != tail.val: return False
head = head.next
tail = tail.next
return True
2. 链表的深度拷贝
对于包含随机指针的链表，执行深度拷贝可能会有些复杂。我们可以通过哈希表或将复制的节点跟在原节点后面的方法来实现。def copy_random_list(head):
if not head: return head
# 复制节点跟在原节点后面
cur = head
while cur:
clone = ListNode(cur.val, cur.next)
cur.next = clone
cur = clone.next
# 处理random指针
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 分离原链表和复制的链表
cur = head
clone_head = cur.next
while cur.next:
temp = cur.next
cur.next = temp.next
cur = temp
return clone_head
3. 链表的重新排列
重新排列链表，例如：给定链表 1->2->3->4，重新排列为 1->4->2->3。我们可以找到中点，然后反转后半部分链表，最后合并两个链表。def reorder_list(head):
if not head: return
# 找到中点
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 反转后半部分链表
prev, cur = None, slow
while cur:
temp = cur.next
cur.next = prev
prev = cur
cur = temp
# 合并两个链表
first, second = head, prev
while second.next:
temp1, temp2 = first.next, second.next
first.next, second.next = second, temp1
first, second = temp1, temp2
第四部分：链表与递归
1. 递归反转整个链表
递归可以很自然地反转整个链表。在递归过程中，我们首先到达链表的末端，然后再逐步反转每个节点。def reverse_list(head):
if not head or not head.next: # 如果链表为空或者只有一个节点，直接返回
return head
last = reverse_list(head.next) # 递归反转下一个节点
head.next.next = head # 将当前节点设置为下一个节点的下一个节点
head.next = None # 将当前节点的下一个节点设置为 None
return last # 返回反转后的头节点
2. 递归反转链表的一部分
我们还可以使用递归来反转链表的一部分。这比反转整个链表稍微复杂一点，因为我们需要记住反转部分的起点和终点。def reverse_between(head, m, n):
if m == 1: # 如果从第一个节点开始反转，则相当于反转整个链表
return reverse_n(head, n)
head.next = reverse_between(head.next, m - 1, n - 1) # 递归处理下一个节点
return head # 返回头节点
def reverse_n(head, n):
successor = None # 用于保存第 n + 1 个节点
if n == 1: # 如果 n 为 1，表示反转部分已完成
successor = head.next # 保存第 n + 1 个节点
return head # 返回头节点
last = reverse_n(head.next, n - 1) # 递归反转下一个节点
head.next.next = head # 将当前节点设置为下一个节点的下一个节点
head.next = successor # 将当前节点的下一个节点设置为第 n + 1 个节点
return last # 返回反转后的头节点
3. 递归地合并两个链表
递归也可以用来合并两个链表。如果我们有两个已排序的链表，我们可以比较它们的头节点，然后递归地合并剩下的节点。def merge_two_lists(l1, l2):
if not l1: return l2 # 如果 l1 为空，直接返回 l2
if not l2: return l1 # 如果 l2 为空，直接返回 l1
if l1.val < l2.val: # 如果 l1 的值小于 l2 的值
l1.next = merge_two_lists(l1.next, l2) # 递归合并 l1 的下一个节点和 l2
return l1 # 返回 l1 作为头节点
else:
l2.next = merge_two_lists(l1, l2.next) # 递归合并 l1 和 l2 的下一个节点
return l2 # 返回 l2 作为头节点
第五部分：链表问题的优化与实际应用
1. 优化
在解决链表问题时，有时候可能会遇到性能问题。优化的方向可能包括减少时间复杂度、空间复杂度或者提高代码的可读性。比如，在合并两个有序链表时，可以通过迭代和递归两种方式，根据具体情况选择更适合的一种。
2. 实际应用
链表在实际应用中的用途广泛，包括实现数据结构（如堆栈和队列）、内存管理、符号表等。理解链表如何工作以及如何有效地使用链表，对于软件开发人员来说是非常重要的。
3. 环形链表的应用
环形链表在实际应用中也很有用。例如，它可以用于实现轮询调度算法。在这个算法中，每个任务被赋予一个优先级，调度器会按照优先级循环选择任务执行。class CircularLinkedList:
def __init__(self):
self.head = None
def add(self, value):
new_node = ListNode(value)
if not self.head:
self.head = new_node
new_node.next = new_node
else:
tail = self.head
while tail.next != self.head:
tail = tail.next
tail.next = new_node
new_node.next = self.head
def rotate(self):
if self.head:
self.head = self.head.next
4. 双向链表的应用
双向链表是链表的一种变体，每个节点都有一个指向前一个节点的指针。双向链表用于实现像浏览器的前进和后退功能这样的应用。class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, value):
new_node = ListNode(value)
if not self.head:
self.head = self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
总结:
本博客全面而深入地探讨了链表这一基础数据结构。我们从链表的基本概念和核心技术入手，逐渐深入到了链表的高级操作和应用，旨在帮助读者全面掌握链表的知识。
在第一部分，我们学习了链表的基础知识，明确了链表的核心点，并通过实例详细解释了如何操作链表，特别是如何处理链表中的哑巴节点和快慢指针。
在第二部分，我们深入探讨了链表的插入、删除、翻转和合并等操作，并介绍了链表分隔的方法，为读者展示了链表的多样性和灵活性。
在第三部分，我们详细探讨了解决链表问题的策略和技巧，帮助读者更加系统地理解和应对各类链表问题。
第四部分着重于链表与递归的结合，通过实例展示了如何使用递归来反转整个链表、反转链表的一部分和合并两个链表。
最后，在第五部分，我们讨论了链表问题的优化方向，并介绍了链表在实际应用中的重要性，包括环形链表和双向链表的应用。
整体而言，本博客为读者提供了一份全面而详实的链表学习材料。无论你是初学者还是有经验的开发者，都能在这里找到有价值的内容。希望本博客能助你一臂之力，让你更加熟练地运用链表解决实际问题。
