题目链接
https://leetcode.cn/problems/reverse-linked-list-ii/
题目解析
方法1：递归算法
思想：将需要旋转的部分取出，利用递归方法（参考：https://editor.csdn.net/md/?articleId=124715935）进行链表反转，然后再与原链表其余部分进行链接。
/**
* 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) {
if(left==right)
{
return head;
}
ListNode dummyNode=new ListNode(-1);
dummyNode.next=head;
ListNode pre=dummyNode;
for(int i=0;i<left-1;i++)
{
pre=pre.next;//左边界的前一个节点
}
ListNode leftNode=pre.next;//左节点
ListNode rightNode=pre;
for(int i=0;i<right-left+1;i++)
{
rightNode=rightNode.next;//右节点
}
ListNode cur=rightNode.next;//右节点的后一个节点
pre.next=null;
rightNode.next=null;
reverseList(leftNode);//旋转列表
pre.next=rightNode;//左节点连接
leftNode.next=cur;//右节点连接
return dummyNode.next;
}
public ListNode reverseList(ListNode leftNode)
{
ListNode head=leftNode;
if(head==null || head.next==null)
{
return head;
}
ListNode curr=reverseList(head.next);
head.next.next=head;
head.next=null;
return curr;
}
}
方法2：遍历
思想：从left遍历到right，在遍历的过程中反转链表
第一步：
第二步：
第三步：
注：上述图片为视频中的截图，具体演示过程可参考https://leetcode.cn/problems/reverse-linked-list-ii/solution/92-fan-zhuan-lian-biao-ii-by-chen-wei-f-sjcn/
/**
* 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) {
if(left==right)
{
return head;
}
ListNode dummyNode=new ListNode(-1);
dummyNode.next=head;
ListNode pre=dummyNode;
for(int i=0;i<left-1;i++)
{
pre=pre.next;//找到左边界的前一个节点
}
ListNode middleNode=pre.next;//找到左节点
ListNode temp;
for(int i=0;i<right-left;i++)
{
temp=middleNode.next;
middleNode.next=temp.next;
temp.next=pre.next;
pre.next=temp;
}
return dummyNode.next;
}
}
