92. 反转链表 II-字节跳动高频题

一、题目描述

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

二、解题

链表拆分+合并

先找到上面四个节点值，然后preleft和leftnode断开，然后在将rightnode和nextright断开，然后将leftnode和rightnode中的链表翻转，然后在合并链表。

/** * 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) {
    
        //定义两个节点，left 的前一个节点，right的后一个节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prelfet = dummy;
        //查找四个节点
        for(int i = 0;i<left-1;i++){
    
            prelfet = prelfet.next;
        }
        ListNode leftnode = prelfet.next;

        ListNode rightnode = prelfet;
        for(int i = 0;i<right-left+1;i++){
    
            rightnode = rightnode.next;
        }
    
        ListNode nextright = rightnode.next;
        //断开链表
        prelfet.next = null;
        rightnode.next = null;
        //翻转链表
        ListNode cur = reverse(leftnode);
        //合并链表
        prelfet.next = cur;
        leftnode.next = nextright;
        return dummy.next;        
    }
    //翻转链表有两种 递归和迭代
    public ListNode reverse(ListNode head){
    
        if(head == null || head.next == null){
    
            return head;
        }
        ListNode cur = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
}