当前位置：首页 > news >正文

力扣经典算法篇-25-反转链表 II(头插法）

news 2025/7/16 16:07:56

1、题干

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

示例 1：
在这里插入图片描述
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]

提示：
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

2、解题

前提给定：（链表节点的定义和链表的形成）

链表节点定义如下：

// 链表节点
public class ListNode {int val;ListNode next;ListNode() {}ListNode(int x) {val = x;}
}

链表构建过程示例：（如上示例1）

public static void main(String[] args) {ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(4);ListNode node5 = new ListNode(5);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;ListNode node = reverseBetween(node1, 2, 4);while (node != null) {System.out.println(node.val);node = node.next;}}

方法一：（头插法）

首先要定义一个新的节点作为合并链表结果的前驱节点，这个前驱节点的下一个节点就是我们处理后的最终链表。
同时要在定义一个和前驱节点指向相同的中间节点，用于生成合并的链表。（生成链表必须是当前节点.next=下一个节点才行，但是这样当前节点也向后移动了）。

链表交换节点的逻辑：
1、定义和找到要交换的两个节点front和next；
2、断开front和next的节点关系，指向next的下一个节点；front.next = next.next;
3、将next插入到头部，头部的第一个节点为pre.next; 所以next.next = pre.next;此时pre和next的下一个节点都是头结点位置；
4、断开pre和头结点的关系，指向next节点，重新生成一条链式关系；pre.next =next;

代码示例：

  public static ListNode reverseBetween(ListNode head, int left, int right) {// 定义用于最终返回的前驱指针ListNode preResult = new ListNode(-1);// 指向目标链表preResult.next = head;// 定义pre指针，用于中间遍历处理ListNode pre = preResult;// 使pre指针指到目标区域的前一个位置for (int i = 0; i < left - 1; i++) {pre = pre.next;}// front为交换区域的第一个节点ListNode front = pre.next;// 遍历次数，进行头插处理for (int i = 0; i < right - left; i++) {// 找到要进行交换的next节点，在fron后面一个节点ListNode next = front.next;// 断开front和next的关系，让front指向next后面的节点front.next = next.next;// 将next插入到头部位置，next节点指向pre的next节点。此时，pre和next都指向头位置next.next = pre.next;// 将pre指向next节点，完成next的头插处理pre.next = next;}return preResult.next;  // 返回前驱节点的下一个节点，处理后的链表头}