Leetcode-每日一题【92.反转链表Ⅱ】
题目
给你单链表的头指针 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.对截取出来的链表进行反转，详情请查看 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;
}
}
