首页4.利用原空间把链表反转，撰写反转函数函数，遍历输出反转后的链表数据，与反转前相比，测试反转的正确与否

4.利用原空间把链表反转，撰写反转函数函数，遍历输出反转后的链表数据，与反转前相比，测试反转的正确与否

时间: 2024-10-16 09:07:23 浏览: 79

在编程中，反转链表是一个常见的操作，特别是当你需要将链表元素的顺序倒置时。这里我会给你展示如何在一个新的递归函数中完成链表的反转，并在遍历过程中检查反转是否成功。首先，我们需要定义一个链表节点的结构： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next ``` 然后编写一个反转链表的递归函数 `reverse_list`： ```python def reverse_list(head): if head is None or head.next is None: # 如果链表为空或只有一个节点，直接返回头节点 return head else: # 创建一个新的头节点，指向当前节点的下一个节点 new_head = reverse_list(head.next) # 反转当前节点的next指针，使其指向前一个节点 head.next.next = head # 更新当前节点的next指针，使其指向None head.next = None return new_head ``` 接下来，我们可以创建一个辅助函数用于遍历并打印链表的值，包括原始链表和反转后的链表： ```python def print_list(head): curr = head while curr: print(curr.val, end=" -> ") curr = curr.next print("None") # 测试反转函数 original_head = ListNode(1, ListNode(2, ListNode(3, ListNode(4)))) reversed_head = reverse_list(original_head) print("Original list:") print_list(original_head) print("\nReversed list:") print_list(reversed_head) ``` 比较两个链表是否相同（即判断它们是否是同一个单向循环）可以额外增加一些逻辑。你可以通过两个指针，一个正常遍历，另一个反转遍历，看它们是否同时到达None。如果都到达了，说明反转正确；如果有一个先到达None，那说明原始链表不是单向循环。

阅读全文