链表是一种基础但非常强大的数据结构，它在编程面试中经常被考察。掌握链表编程不仅能帮助你轻松应对面试中的难题，还能提升你的编程能力。本文将为你提供50个经典的链表编程练习题及解答攻略，让你在面试中游刃有余。
1. 反转链表
题目描述： 反转一个单链表。
解答：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = 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. 删除链表的倒数第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.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
4. 链表中的中间节点
题目描述： 找到链表中的中间节点。
解答：
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
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 delete_duplicates(head):
dummy = ListNode(0)
dummy.next = head
current = dummy
while current.next and current.next.next:
if current.next.val == current.next.next.val:
current.next = current.next.next
else:
current = current.next
return dummy.next
7. 链表的倒数第K个节点
题目描述： 返回链表的倒数第K个节点。
解答：
def get_kth_from_end(head, k):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
for _ in range(k):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
return slow
8. 分隔链表
题目描述： 将链表分隔为两个大小相等的部分。
解答：
def partition(head, x):
dummy1 = ListNode(0)
dummy2 = ListNode(0)
current1 = dummy1
current2 = dummy2
while head:
if head.val < x:
current1.next = head
current1 = current1.next
else:
current2.next = head
current2 = current2.next
head = head.next
current2.next = None
current1.next = dummy2.next
return dummy1.next
9. 链表的奇偶节点重排
题目描述： 将链表的奇偶节点重新排列。
解答：
def odd_even_list(head):
if not head or not head.next:
return head
odd, even, even_head = head, head.next, head.next
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
10. 回文链表
题目描述： 判断链表是否为回文链表。
解答：
def is_palindrome(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev = None
while slow:
next_node = slow.next
slow.next = prev
prev = slow
slow = next_node
return head == prev or head.next == prev
总结
以上是10个经典的链表编程练习题及解答攻略，涵盖了链表的基本操作和常见面试题。通过学习和练习这些题目，你可以提升自己的链表编程能力，并在面试中取得好成绩。祝你在编程道路上越走越远！