石家庄 做网站百度一下官方网址

题目描述：

给你单链表的头指针 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]

代码实现：

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode tmp = new ListNode(-1);// 设置哑结点tmp.next = head;// 哑结点指向头节点// pre指向哑结点ListNode pre = tmp;// 使pre指向反转链表的前一个结点for (int i = 0; i < left - 1; i++) {pre = pre.next;}ListNode rightNode = pre;// 记录反转链表的前一个结点for (int i = 0; i < right - left + 1; i++) {rightNode = rightNode.next;// 找到反转链表的尾结点}ListNode leftNode = pre.next;// 记录反转链表的头节点ListNode endList = rightNode.next;// 记录反转链表的后一个结点// 断开原来链表：将需要反转的链表切割开pre.next = null;// 切割头节点rightNode.next = null;// 切割尾结点// 反转链表操作reverseLinkedList(leftNode);// 连接链表操作pre.next = rightNode;// 原先反转链表的前驱 指向 现在反转之后的链表的右节点（也就是现在的头节点）leftNode.next = endList;// 反转之后的链表左节点（也就是现在的尾结点） 指向 原先反转链表的后继// 返回哑结点的后继return tmp.next;// 这里不返回head结点的原因是：在反转操作时，head已经指向反转链表的尾结点了}// 反转函数反转了结点之间的指向，head指向的是反转之后的尾结点void reverseLinkedList(ListNode head) {ListNode cur = head;// 头节点开始遍历ListNode pre = null;// 前驱结点while (cur != null) {ListNode next = cur.next;// 记录后继结点cur.next = pre;// 结点指向前驱pre = cur;// 前驱指针指向当前结点cur = next;// 当前指针指向后继结点}}
}