首页不带头结点的单链表反转

不带头结点的单链表反转

时间: 2025-01-26 09:07:14 AIGC 浏览: 46

不带头结点的单链表反转是指将一个单链表的节点顺序进行反转，使得最后一个节点变为第一个节点，第一个节点变为最后一个节点。以下是实现不带头结点的单链表反转的步骤和代码示例： 1. **定义链表节点结构**：首先，我们需要定义一个链表节点的结构，每个节点包含一个数据部分和一个指向下一个节点的指针。 2. **初始化链表**：创建一个不带头结点的单链表，并初始化一些节点。 3. **反转链表**：使用三个指针来反转链表：prev、current和next。prev用于记录前一个节点，current用于遍历链表，next用于暂存下一个节点。 4. **更新头指针**：反转完成后，更新链表的头指针为prev。以下是具体的代码示例： ```python class ListNode: def __init__(self, data=0, next=None): self.data = data self.next = next 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 def print_linked_list(head): current = head while current: print(current.data, end=" -> ") current = current.next print("None") # 初始化链表 head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))) print("原链表:") print_linked_list(head) # 反转链表 reversed_head = reverse_linked_list(head) print("反转后的链表:") print_linked_list(reversed_head) ``` 运行上述代码，输出结果如下： ``` 原链表: 1 -> 2 -> 3 -> 4 -> 5 -> None 反转后的链表: 5 -> 4 -> 3 -> 2 -> 1 -> None ```

阅读全文