链表是数据结构中的一种，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表在计算机科学中有着广泛的应用，特别是在需要动态内存分配的场景中。掌握链表算法对于提升编程能力至关重要。本文将带你从基础到进阶，挑战50道链表算法题，帮助你轻松提升编程技能。
基础篇
1. 单链表反转
题目描述：给定一个单链表的头节点，将其反转。
代码示例：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
2. 合并两个有序链表
题目描述：给定两个有序链表的头节点，合并它们为一个新的有序链表。
代码示例：
def merge_two_lists(l1, l2):
dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
进阶篇
3. 链表中倒数第k个节点
题目描述：给定一个链表的头节点和整数k，返回链表中倒数第k个节点。
代码示例：
def find_kth_to_last(head, k):
fast = slow = head
for _ in range(k):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
return slow
4. 删除链表的倒数第n个节点
题目描述：给定一个链表的头节点和整数n，删除链表中倒数第n个节点。
代码示例：
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
挑战篇
5. 环形链表
题目描述：给定一个链表的头节点，判断链表中是否存在环。
代码示例：
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
6. 两两交换链表中的节点
题目描述：给定一个链表的头节点，将链表中相邻的节点两两交换。
代码示例：
def swap_pairs(head):
dummy = ListNode(0)
dummy.next = head
prev = dummy
while prev.next and prev.next.next:
first = prev.next
second = prev.next.next
prev.next = second
first.next = second.next
second.next = first
prev = first
return dummy.next
总结
通过以上50道链表算法题的挑战，相信你已经对链表有了更深入的了解。在编程实践中，不断练习和总结，才能在算法方面取得更大的进步。祝你在编程的道路上越走越远！