“This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Reverse Linked List II

LeetCode Portal 92. Reverse linked list II

The title

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.

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example:


Input: head = [1.2.3.4.5], left = 2, right = 4
Output: [1.4.3.2.5]



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

Constraints:

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

Thinking line

Their thinking

How do we solve this problem?

The first thing we need to know is how to invert a linked list from beginning to end, and if you’re not sure how to do that you can refer to this video that I did on Station B and the link is here, right

Now that we know how to reverse a list from start to end, let’s assume that the left node is the head and the right node is the tail. We can reverse the list from left to right.

After reversing the left to right list, the question is how to get the reversed list chain to take the unreversed head and tail

We can consider the following cases:

Let’s start with the head:

  • ifleft ! = = 1That means there is an uninverted head, and we record the position of the headpreLeftNodeAfter the flip is done, turn thepreLeftNodeIt points to the flipped head, but the head of the whole list hasn’t changedhead
  • ifleft ===1It means that there is no unreversed head, then the head has changed, and the head is reversed linked listreversedIn the head.

Let’s look at what happens at the tail:

  • ifRight === end of the list, indicates the linked list after inversionreversedThe tail is going to be the tail of our final list. Here we flip the linked listreversedThe tail of theleftNodethenextPointer tonullOtherwise the linked list will have loops.
  • ifright ! == end of the linked list, indicates the linked list after inversionreversedThe tail needs to be linked to the original listrightNodeThe next node of. Here we flip the linked listreversedThe tail of theleftNodethenextThe pointer points to the next node in the original list.

At this point, we have completed the logic of flipping the list, and finally we can return the new header.

The following code

/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val? : number, next? : ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */

function reverseBetween(head: ListNode | null, left: number, right: number) :ListNode | null {
    let list = head;
    let i = 0
    let pre: ListNode | null; // The previous one in the rollover process
    let next: ListNode | null; // The last one in the rollover process
    let preLeftNode: ListNode | null; // The first node left in the original list
    let leftNode: ListNode | null; // left the corresponding node
    let rightNode: ListNode | null; // The node corresponding to right
    let rNext: ListNode | null; // The next node corresponding to right in the original list
    while (list) {
        i++;
        if (i === left - 1) preLeftNode = list;
        if (i === left) {
            pre = list;
            leftNode = list;
            next = pre.next;
        }
        if (i === right) {
            rightNode = list;
            if (list.next) rNext = list.next;
            break;
        }
        list = list.next;
    }

	// Reverse the list from left to right
    while(next && pre ! == rightNode) {const temp = next.next;
        next.next = pre;
        pre = next;
        next = temp;
    }
    let newHead: ListNode | null;;

	// Handle the header logic
    if (preLeftNode) {
        newHead = head;
        preLeftNode.next = pre;

    } else {
        newHead = pre;
    }
	// Handle tail logic
    if (rNext) {
        leftNode.next = rNext;
    }else {
        leftNode.next = null;
    }


    return newHead;

};
Copy the code

This is my first version of the code, so how can we optimize the code for this idea?

To reduce the number of headers we can add a dummyHead to the list dummyHead so that our new head node always points to dummyhead.next.

And what about our tail point? We can observe that whether rNext points to NULL or there is a node, we just need to point the flipped node tail to rNext, so we can get a slightly optimized code, as shown below

function reverseBetween(head: ListNode | null, left: number, right: number) :ListNode | null {
    const dummyHead = new ListNode(0);
    dummyHead.next = head;
    let i = 0
    let pre: ListNode | null; // The previous one in the rollover process
    let next: ListNode | null; // The last one in the rollover process
    let preLeftNode: ListNode | null; // The first node left in the original list
    let leftNode: ListNode | null; // left the corresponding node
    let rightNode: ListNode | null; // The node corresponding to right
    let rNext: ListNode | null = null; // The next node corresponding to right in the original list
    if (left === 1) preLeftNode = dummyHead;
    while (head) {
        i++;
        if (i === left - 1) preLeftNode = head;
        if (i === left) {
            pre = head;
            leftNode = head;
            next = pre.next;
        }
        if (i === right) {
            rightNode = head;
            if (head.next) rNext = head.next;
            break;
        }
        head = head.next;
    }

    // Reverse the list from left to right
    while(next && pre ! == rightNode) {const temp = next.next;
        next.next = pre;
        pre = next;
        next = temp;
    }
    preLeftNode.next = pre;
    leftNode.next = rNext;


    return dummyHead.next;

};
Copy the code

Time complexity analysis

O(n): where n is the total node of the list, and in the worst case, the entire list needs to be traversed.

This is my solution to this question. If you have any questions or better solutions, please leave a comment and interact.