Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

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:

Their thinking

There are two ways: because both methods use virtual head nodes, also known as sentinels. In this question, the role of virtual head nodes is to facilitate the processing of special operations on the linked list. All possible operations to the linked list head nodes can be set up with a virtual head node.

A: iterative method, last time to reverse the dynamic diagram of the linked list, can be deduced from one example, this oral steps:

  1. First we define a virtual head node called RET and point it to our real head node.
  2. Define a node p = ret.
  3. We need to find the head node with the inversion region according to left
  4. Followed and inversion lists 206 train of thought is consistent, but the loop termination conditions the total number of nodes need to rely on reverse area, at the end of the cycle can not directly back to the pre, it would have been lost not reverse part of nodes, so after the interval inversion, need to the original head head node (that is, the end node) after the reverse pointer to cur
  5. The next step is to execute the reverseList1 function we defined and return ret.next (virtual header next points to the original list head node).

Recursion: the recursive function is expressed by reverseList. The recursion mode conforms to the advanced order, and only one iteration is used. The difference between the 206 reverseList and the reverseList is also the termination condition of recursion.

The problem solving code

// The iterative encapsulation method
var reverseList1 = function (head, n) {
    let [pre, cur] = [null, head];
    while (n--) {
        [cur.next, pre, cur] = [pre, cur, cur.next];
    }
    head.next = cur;
    return pre;
}

var reverseList = function (head, n) {
    if (n === 1) return head;
    let tail = head.next, p = reverseList(head.next, n - 1);
    head.next = tail.next;
    tail.next = head;
    return p;
}

var reverseBetween = function (head, left, right) {
    let cnt = right - left + 1;
    let ret = new ListNode(0, head), p = ret;
    while (--left) p = p.next;
    // p.next = reverseList(p.next, cnt);
    p.next = reverseList1(p.next, cnt);
    return ret.next;
};
Copy the code

conclusion

Recently learned the linked list this kind of data structure, in order to consolidate, the current several are specialized in the linked list algorithm, if there are mistakes in the article, forget to point out.