本文目录导读：
我来为你提供几个Python链表遍历的实操案例,从基础到进阶。
基础链表类定义
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def append(self, val):
"""在链表末尾添加节点"""
new_node = ListNode(val)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def display(self):
"""遍历并打印链表"""
values = []
current = self.head
while current:
values.append(str(current.val))
current = current.next
print("->".join(values))
基本遍历操作
# 创建示例链表
ll = LinkedList()
for i in range(1, 6):
ll.append(i)
# 遍历链表
print("原始链表:")
ll.display() # 1->2->3->4->5
# 方法1：while循环遍历
def traverse_while(head):
"""使用while循环遍历"""
current = head
while current:
print(f"节点值: {current.val}", end=" ")
current = current.next
print()
# 方法2：递归遍历
def traverse_recursive(node):
"""递归遍历链表"""
if not node:
return
print(f"节点值: {node.val}", end=" ")
traverse_recursive(node.next)
print("while循环遍历:")
traverse_while(ll.head)
print("递归遍历:")
traverse_recursive(ll.head)
print()
常见遍历操作案例
案例1：查找元素
def search_linked_list(head, target):
"""在链表中查找目标值"""
current = head
position = 0
while current:
if current.val == target:
return position
current = current.next
position += 1
return -1
# 测试
print(f"查找值3的位置: {search_linked_list(ll.head, 3)}") # 2
print(f"查找值10的位置: {search_linked_list(ll.head, 10)}") # -1
案例2：计算链表长度
def get_length(head):
"""计算链表长度"""
count = 0
current = head
while current:
count += 1
current = current.next
return count
def get_length_recursive(node):
"""递归计算链表长度"""
if not node:
return 0
return 1 + get_length_recursive(node.next)
print(f"链表长度: {get_length(ll.head)}") # 5
print(f"链表长度(递归): {get_length_recursive(ll.head)}") # 5
案例3：求和与平均值
def sum_linked_list(head):
"""计算链表所有节点的和"""
total = 0
current = head
while current:
total += current.val
current = current.next
return total
def average_linked_list(head):
"""计算链表平均值"""
total = 0
count = 0
current = head
while current:
total += current.val
count += 1
current = current.next
return total / count if count > 0 else 0
print(f"节点和: {sum_linked_list(ll.head)}") # 15
print(f"平均值: {average_linked_list(ll.head):.2f}") # 3.00
案例4：反转链表（遍历方式）
def reverse_linked_list(head):
"""反转链表"""
prev = None
current = head
while current:
next_node = current.next # 保存下一个节点
current.next = prev # 反转指针
prev = current # 移动prev
current = next_node # 移动current
return prev
# 测试反转
print("原链表:")
ll.display()
new_head = reverse_linked_list(ll.head)
print("反转后:")
current = new_head
while current:
print(current.val, end=" ")
current = current.next
print()
案例5：删除指定值
def remove_elements(head, val):
"""删除链表中所有值为val的节点"""
# 处理头节点
while head and head.val == val:
head = head.next
# 遍历删除
current = head
while current and current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return head
# 创建测试链表
test_ll = LinkedList()
for i in [1, 2, 6, 3, 4, 5, 6]:
test_ll.append(i)
print("原链表:")
test_ll.display()
test_ll.head = remove_elements(test_ll.head, 6)
print("删除6后:")
test_ll.display()
案例6：合并两个有序链表
def merge_two_lists(l1, l2):
"""合并两个有序链表"""
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
# 连接剩余部分
current.next = l1 if l1 else l2
return dummy.next
# 创建两个有序链表
ll1 = LinkedList()
ll2 = LinkedList()
for i in [1, 3, 5]:
ll1.append(i)
for i in [2, 4, 6]:
ll2.append(i)
print("链表1:", end=" ")
ll1.display()
print("链表2:", end=" ")
ll2.display()
merged_head = merge_two_lists(ll1.head, ll2.head)
print("合并后:")
current = merged_head
while current:
print(current.val, end=" ")
current = current.next
print()
高级遍历技巧
class AdvancedLinkedList:
"""带高级功能的链表类"""
def __init__(self):
self.head = None
def from_list(self, lst):
"""从列表构建链表"""
if not lst:
return
self.head = ListNode(lst[0])
current = self.head
for val in lst[1:]:
current.next = ListNode(val)
current = current.next
def traverse_with_index(self):
"""带索引的遍历"""
current = self.head
index = 0
while current:
yield index, current.val
current = current.next
index += 1
def traverse_two_pointers(self):
"""快慢指针遍历"""
slow = fast = self.head
result = []
while fast and fast.next:
result.append((slow.val, fast.val))
slow = slow.next
fast = fast.next.next
return result
# 使用示例
adv_ll = AdvancedLinkedList()
adv_ll.from_list([1, 2, 3, 4, 5, 6])
print("带索引遍历:")
for index, val in adv_ll.traverse_with_index():
print(f"索引 {index}: {val}")
print("\n快慢指针遍历:")
pairs = adv_ll.traverse_two_pointers()
for slow_val, fast_val in pairs:
print(f"慢指针: {slow_val}, 快指针: {fast_val}")
实际应用场景
# 场景1：数据备份检查
def check_data_integrity(head):
"""检查链表数据的完整性"""
current = head
previous_val = None
while current:
if previous_val and current.val < previous_val:
return False, f"数据异常: {previous_val} -> {current.val}"
previous_val = current.val
current = current.next
return True, "数据完整"
# 场景2：寻找中间节点
def find_middle_node(head):
"""快慢指针找中间节点"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.val if slow else None
# 测试
test_data = LinkedList()
for i in [1, 2, 3, 4, 5]:
test_data.append(i)
print("数据检查:", check_data_integrity(test_data.head))
print("中间节点:", find_middle_node(test_data.head))
这些案例涵盖了链表遍历的主要操作场景,建议你：
- 先理解每个案例的逻辑
- 自己动手实现一遍
- 尝试修改代码以适应不同需求
- 练习手写链表遍历的代码
常见的面试题也会基于这些基础操作进行变形,多练习就能熟练掌握。
标签： 案例实操
