PPT动画之每天一算：Reverse Linked List
最新回答
探春
2024-01-27 05:07:58
反转单链表是数据结构中的经典问题，可通过迭代和递归两种方式实现。以下是对该问题的详细解答：
迭代法- 核心思想：通过调整节点指针方向实现反转。
- 步骤：
初始化三个指针：pre（前驱节点，初始为NULL）、cur（当前节点，初始为头节点head）、next（临时存储下一节点）。
遍历链表，每次保存cur->next到next，然后将cur->next指向pre，完成局部反转。
移动pre和cur指针：pre移至cur，cur移至next。
重复上述步骤直到cur为NULL，此时pre指向新链表的头节点。
- 代码实现：ListNode* reverseList(ListNode* head) { ListNode* pre = NULL; ListNode* cur = head; while (cur != NULL) { ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre;}
- 复杂度：时间复杂度O(n)，空间复杂度O(1)。
- 核心思想：从链表末尾开始反转指针方向。
- 步骤：
终止条件：若链表为空或仅有一个节点，直接返回头节点。
递归调用：反转剩余链表（head->next），得到新的头节点rhead。
局部反转：将当前节点的下一节点（head->next）的next指向当前节点，形成双向指针。
断开原指针：将当前节点的next置为NULL，避免循环。
返回新头节点rhead。
- 代码实现：ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode* rhead = reverseList(head->next); head->next->next = head; head->next = NULL; return rhead;}
- 复杂度：时间复杂度O(n)，空间复杂度O(n)（递归栈开销）。
- 迭代法：通过调整指针方向逐步反转，需注意指针移动顺序。
- 递归法：从后向前反转，需理解递归栈的回溯过程。
- 边界条件：处理空链表或单节点链表时直接返回。
- 动画：展示了迭代过程中指针的变化（如pre、cur、next的移动和指针方向调整）。
- 执行结果：两种方法均能正确反转链表，并通过LeetCode测试用例验证。
- 输入：1->2->3->4->5->NULL
- 输出：5->4->3->2->1->NULL
通过以上方法，可高效实现单链表的反转，适用于需要逆序处理链表的场景。
热门标签
