LeetCode刷题 92反转链表 II

92. 反转链表 II

难度中等1250收藏分享切换为英文接收动态反馈

给你单链表的头指针 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

进阶： 你可以使用一趟扫描完成反转吗？

题解（三指针+头插）

• 必须要先将tail后面的node结点从链表中删除，再头插到prev之后

JAVA实现代码

      public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode dummyHead=new ListNode();
        dummyHead.next=head;
        ListNode prev=dummyHead;
        for (int i = 0; i < left-1; i++) {
            prev=prev.next;
        }
        ListNode tail=prev.next;
        ListNode node=tail.next;
        int size=right-left;
        while (size>0){
            //先删除再插入
            tail.next=node.next;
            node.next=prev.next;
            prev.next=node;
            node=tail.next;
            size--;
        }
        return dummyHead.next;
    }

题解（递归） 

  //反转区间right的后续结点
    ListNode sucessor=null;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left==1){
           return reverseN(head,right);
        }
        //如果left!=1说明头结点肯定不是要反转的结点
        head.next=reverseBetween(head.next,left-1,right-1);
        return head;

    }
    //将前n个结点反转
    public ListNode reverseN(ListNode head,int n)  {
        if (n==1){
            sucessor=head.next;
            return head;
        }
        ListNode next=head.next;
        ListNode nextHead=reverseN(head.next,n-1);
        next.next=head;
        head.next=sucessor;
        return nextHead;
    }