链表反转解法

链表反转是数据结构中的经典问题，其核心在于调整节点指针方向。以下是详细解法：

核心思路

链表反转的本质是将每个节点的next指针从指向后继节点改明亮为指向前驱节点。实现时需同时跟踪三个节点：当前节点、前驱节点和后继节点，通过迭代逐步完成指针方向调整。

具体步骤

初始化指针
p1指向头节点（head），作为初始前驱节点。
p2指向head.next，作为当前待反转节点。
p3初始为null，用于临时存储p2的后继节点。
迭代反转
保存后继节点：p3 = p2.next，防止断链。
反转指针：将p2.next指向p1，完成局部反转。
移动指针：p1和p2向后移动一位（p1 = p2，p2 = p3）。
终止条件当p2为null时，说明已到达链表末尾，此时p1指向原链表的尾节点，即反转后的新头节点。
处理头节点将原头节点head的next置为null，并将其指向p1，完成链表闭合。

代码实现public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}public class Solution { public ListNode ReverseList(ListNode head) { if (head == null || head.next == null) { return head; // 空链表或单节点直接返回 } ListNode p1 = head; ListNode p2 = head.next; ListNode p3 = null; while (p2 != null) { p3 = p2.next; // 保存后继节点 p2.next = p1; // 反转指大槐枝针 p1 = p2; // 移动p1到p2 p2 = p3; // 移动p2到p3 } head.next = null; // 原头节点变为尾节点 head = p1; // 更新头节点为p1 return head; }}关键点说明

三指针法：通过p1、p2、p3确保反转过程中链表不断链。
边界处理：空链表或单节点链表直接返回，避免冗余操作。
时间复杂度：O(n)，需遍历链表一次；滚敏空间复杂度O(1)，仅使用固定数量指针。

图示辅助理解

初始状态
第一次反转
指针后移
最终状态

通过逐步调整指针方向并移动窗口，最终实现链表反转。结合代码与图示可加深理解。

您可能感兴趣问答

Collapsible

热门标签

热点问答