current position:Home>Force deduction algorithm - 92 Reverse linked list II

Force deduction algorithm - 92 Reverse linked list II

2022-01-26 22:40:20 TyuIn

subject :

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:
 Insert picture description here
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]

Tips :

  • The number of nodes in the linked list is n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Advanced : Can you use one scan to complete the inversion ?

class Solution {
    
    public ListNode reverseBetween(ListNode head, int left, int right) {
    
        //  Reverse from position  left  To  right  Linked list node between 
        ListNode node = new ListNode(-1);
        node.next = head;
        //  Record the nodes on the left that do not need to be reversed 
        ListNode pre = node;
        for(int i = 1;i < left;i++){
    
            pre = pre.next;
        }
        //  Exclude nodes on the left that do not need to be reversed 
        head = pre.next;
        //  reverse  left,right  Nodes in the interval 
        for(int i = left;i < right;i++){
    
            ListNode tem = head.next;
            head.next = tem.next;
            tem.next = pre.next;
            pre.next = tem;
        }
        return node.next;
    }
}

 Insert picture description here

copyright notice
author[TyuIn],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201262240136880.html

Random recommended