“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

The reverse linked list II is shown below:

Give you the head pointer to the singly linked list head and two integers left and right, where left <= right. Reverse the list node from position left to position right to return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4Copy the code

Example 2:

Input: head = [5], left = 1, right = 1 output: [5]Copy the code

A, thinking

Reverse the left to right positions of the elements in the linked list

So for linked list problems like this, we don’t have to write any code, we can draw a picture of what the subset needs.

There are at least four things we need to know:

Head = [1,2,3,4,5], left = 2, right = 4

  1. leftHead: points to the previous node in the list that has not been reversed. (hereleftHeadYou need to point to the first node1)
  2. rightHead: points to unreversed nodes later in the list. (This points to the last unreversed node5)
  3. newLeftHead: the first element pointing to the inversion position. Since this is the first element of the inversion, this points to the second-to-last element4)
  4. newRightHead: The last element pointing to the inversion position. (Again, we point to the second element because we need to reverse it2)

The four Pointers are shown in the figure below:

Because of the simple inversion of the list, we just need to put the added element at the top of the list. Therefore, in our analysis, we can temporarily ignore the nodes that reverse left ~ right positions

As shown in the figure above, once we have these four Pointers, it’s pretty easy to manipulate. Simply merge the result to which the pointer points.

  1. newRightHead.next = rightHead
  2. leftHead.next = newLeftHead.next

So how do we find these four Pointers? Just go through the following steps:

  1. Walking through the linked list and counting,countRepresents the position of the current node,nextRepresents the current node
  2. whencount < leftUpdate:leftHead = next
  3. whencount == leftUpdate:newRightHeadBecause the first element added is the rightmost element in the result
  4. whencount > right:rightHead = nextJust point to the first unreversed element on the right

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode newLeftHead = new ListNode();
        ListNode newRightHead = newLeftHead;
        ListNode leftHead = null;
        ListNode rightHead = null;
        ListNode next = head;
        int count = 1;
        while(next ! =null) {
            if (count < left) { // left points to the node before the inversion
                leftHead = next;
            } else if (count >= left && count <= right) {
                ListNode temp =new ListNode(next.val);
                temp.next = newLeftHead.next;
                newLeftHead.next = temp;
                if (count == left) {
                    newRightHead = newRightHead.next;   // Right points to the first added node}}if (count > right){
                rightHead = next;
                break;
            }
            next = next.next;
            count++;
        }
        newRightHead.next = rightHead;
        if (leftHead == null) { // There is no element at the beginning of the list
            return newLeftHead.next;
        }else {
            leftHead.next = newLeftHead.next;
            returnhead; }}Copy the code

The test code

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1.new ListNode(2.new ListNode(3.new ListNode(4.new ListNode(5 )))));
        ListNode listNode1 = new ListNode(5);
        new Number92().reverseBetween(listNode, 2.4);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section