92. Reverse linked list II byte skipping high frequency question

One 、 Title Description

Give you the head pointer of the single linked list head And two integers left and right , among left <= right . Please reverse from position left To the position right The linked list node of , return Inverted list .

Example 1：

 Input ：head = [1,2,3,4,5], left = 2, right = 4
 Output ：[1,4,3,2,5]

Example 2：

 Input ：head = [5], left = 1, right = 1
 Output ：[5]

Two 、 Problem solving

Linked list splitting + Merge

First find the above four node values , then preleft and leftnode To break off , And then the rightnode and nextright To break off , And then leftnode and rightnode Flip the linked list in , Then merge the linked list .

/** * 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) {
    
        // Define two nodes ,left  Previous node of ,right Next node of 
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prelfet = dummy;
        // Find four nodes 
        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;
        // Disconnect list 
        prelfet.next = null;
        rightnode.next = null;
        // Flip list 
        ListNode cur = reverse(leftnode);
        // Merge list 
        prelfet.next = cur;
        leftnode.next = nextright;
        return dummy.next;        
    }
    // There are two ways to flip a linked list   Recursion and iteration 
    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;
    }
}