92. 反转链表II

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
示例 1:
img
1
输入:head = [1,2,3,4,5], left = 2, right = 4
2
输出:[1,4,3,2,5]
Copied!
示例 2:
1
输入:head = [5], left = 1, right = 1
2
输出:[5]
Copied!
提示:
    链表中节点数目为 n
    1 <= n <= 500
    -500 <= Node.val <= 500
    1 <= left <= right <= n

题解

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
class Solution {
12
public ListNode reverseBetween(ListNode head, int left, int right) {
13
ListNode dummyNode = new ListNode(0);
14
dummyNode.next = head;
15
ListNode pre = dummyNode;
16
for(int i = 0;i < left -1;i++){
17
pre = pre.next;
18
}
19
//将链表拆分成3个链表
20
//pre左边链表的最后一个节点
21
//leftNode 和rightNode是中间节点的左边节点和右边节点
22
//succ 是右边链表的第一个节点
23
ListNode leftNode = pre.next;
24
ListNode rightNode = pre;
25
for(int i = 0;i < right - left + 1;i++){
26
rightNode = rightNode.next;
27
}
28
//后继者
29
ListNode succ = rightNode.next;
30
pre.next = null;
31
rightNode.next = null;
32
//翻转左边节点
33
reverse(leftNode);
34
pre.next = rightNode ;
35
leftNode.next = succ ;
36
return dummyNode.next;
37
}
38
public void reverse(ListNode head){
39
ListNode pre = null;
40
ListNode cur = head;
41
while(cur!=null){
42
ListNode next = cur.next;
43
cur.next = pre;
44
pre = cur;
45
cur = next;
46
}
47
}
48
}
Copied!
最近更新 3mo ago
复制链接