题目
给你单链表的头指针 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
解题思路
举个栗子:
输入:head = [1,2,3,4,5,6,7], left = 2, right = 5
输出:[1,5,4,3,2,6,7]
1.首先我们设置一个头节点(dummy),让 dummy.next = head
2.我们再设置一个临时节点(dev),让它指向我们的 dummy ,从 dummy 开始遍历来找出 需要反转部分的前一个结点,
(for(int i = 1; i < left; i++){
dev = dev.next;
})
此道题需要反转的部分为[2,3,4,5],我们需要找到 2 之前的结点也就是1
3.dev的next节点就是我们要反转链表的左节点,所以我们设置一个 leftNode ,使dev.next = leftNode ,再设置一个rightNode ,让rightNode 从dev开始遍历 找出 反转部分的右节点
ListNode leftNode = dev.next;
ListNode rightNode = dev;
for(int i = 0; i < right - left + 1; i++){
rightNode = rightNode.next;
}
4.找到需要反转部分的链表后,我们设置一个 rightNext 节点将 rightNode 的 next 保存起来,之后我们将需要反转部分的链表从原链表中截取出来,
ListNode rightNext = rightNode.next;
dev.next = null;
rightNode.next = null;
5.对截取出来的链表进行反转,详情请查看【206.反转链表】
reverseList(leftNode);
6.将链表的前半部分和后半部分与反转链表进行拼接
dev.next = rightNode;
leftNode.next = rightNext;
return dummy.next;
代码实现
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode dev = dummy;
for(int i = 1; i < left; i++){
dev = dev.next;
}
ListNode rightNode = dev;
for(int i = 0; i < right - left + 1; i++){
rightNode = rightNode.next;
}
ListNode leftNode = dev.next;
ListNode rightNext = rightNode.next;
dev.next = null;
rightNode.next = null;
reverseList(leftNode);
dev.next = rightNode;
leftNode.next = rightNext;
return dummy.next;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while(cur != null){
ListNode curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
return prev;
}
}
测试结果