leetcode 92. Reverse linked list II

difficulty ： secondary
The frequency of ：116
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 .

Their thinking ： Reverse a linked list + Traverse

Be careful ：

• Simple implementation of linked list inversion 【 The first interpolation , There are many other ways , But the error rate is low , There are many places to use 】
  - Virtual header node However, it is necessary to consider the left and right boundary nodes , It's right to use virtual nodes
  - In fact, that is g p Two fixed nodes , Then a mobile node temp
  - g Is used to connect inverted nodes ,p The node of has only one function , Point to the next node that needs to be reversed
  - This head insertion method , The last part is also connected

/** * 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 reverseList(ListNode head) {
    
        ListNode dummyhead=new ListNode(-1);
        dummyhead.next=head;
        ListNode p=head,g=dummyhead;
        if(head==null) return head;
        while(p.next!=null){
    // Here is chosen p.next A big reason is p Point to the next node to be reversed 
            ListNode temp=p.next;
            p.next=temp.next;

            temp.next=g.next;
            g.next=temp;
        }
        return dummyhead.next;
    }
}

• The number of numbers between two numbers ： x To y There are many numbers in total =y-x+1, such as 1-100 Altogether =100-1+1 A digital
• Move first g and p To where we need to reverse

Code

/** * 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) {
    
        ListNode dummyhead=new ListNode(-1);
        dummyhead.next=head;
        ListNode g=dummyhead,p=head;
        for(int i=0;i<left-1;i++){
      //p spot ( Actually, the location is 1) Number of moves   from left-1+1-1
            g=g.next;
            p=p.next;
        }
        for(int j=0;j<right-left+1-1;j++){
    
            ListNode temp=p.next;
            p.next=temp.next;
            
            temp.next=g.next;
            g.next=temp;
            //p.g It's all immovable , Only other nodes move 

        }
        return dummyhead.next;
    }
}