92. 反转链表II
题目描述
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
示例 1:
![img](https://assets.leetcode.com/uploads/2021/02/19/rev2ex2.jpg)
| 输入: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
题解
| /**
* 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 dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pre = dummyNode;
for(int i = 0;i < left -1;i++){
pre = pre.next;
}
//将链表拆分成3个链表
//pre左边链表的最后一个节点
//leftNode 和rightNode是中间节点的左边节点和右边节点
//succ 是右边链表的第一个节点
ListNode leftNode = pre.next;
ListNode rightNode = pre;
for(int i = 0;i < right - left + 1;i++){
rightNode = rightNode.next;
}
//后继者
ListNode succ = rightNode.next;
pre.next = null;
rightNode.next = null;
//翻转左边节点
reverse(leftNode);
pre.next = rightNode ;
leftNode.next = succ ;
return dummyNode.next;
}
public void reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur!=null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
}
|