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

Let’s start with a scene

  1. Turn on the force snap brush algorithm
  2. A list of simple problems, full of confidence, directly began to masturbation code
  3. Backhand a submission, directly error
  4. Then began to look for bugs, looking for a long time or error
  5. Finally the mentality collapsed, closed the force button to continue to touch the fish…

The above is the situation I encountered at the beginning of the brush problem. In fact, when doing linked list problems, it is best to clear your mind by drawing pictures, otherwise it is easy to confuse yourself. Let’s look at some algorithms related to reverse linked lists.

Let’s start with the easy ones

206. Reverse linked lists

Analysis of the

  • Given by the problemExample 1So, for example, if you want to get an inverted list then1 nodesWill eventually point tonull
  • So let’s create a new pointerpPoint to thenull
  • Create another oneqPointer toheadConvenient reversal operation later

  • If you want to1 nodesPoint to thenullCannot be directly modifiedq.next = p, this will break the linked list, lost from2 nodesThe opening quote. Need a variable to receive, so willheadMove backwards get2 nodesThe reference,head = head.next

  • You can do it right now1 nodesthenextPoint to thenull.q.next = p

  • thenpandqThe needle moves back,p = q.q = head, avoid the assignment order can not be reversed, so complete1 nodesThe reversal of the

  • Repeat the above steps to complete the inversion. Take a look at the GIF

  • The last returnPointer to the pIt’s a linked list reversed

Code implementation

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    var p = null, q = head
    while(q) { // The order cannot be reversed, otherwise references will be lost
        head = head.next
        q.next = p
        p = q
        q = head
    }
    return p
};
Copy the code
  • It’s easy to write code based on the above image analysis, so make it more difficult

Advanced intermediate problems

92. Reverse linked list II

Analysis of the

  • With the experience of the previous problem, this problem only adds the position and number of inversion, and does not need to reverse the whole list. The main focus is, how to break the list into partial inversion, and then connect back to the original list
  • In order toExample 1For example, first define a virtual head noderetPoint to theheadThe purpose is to make it easy to return, because you can start at the beginning and reverse and end up just returningret.nextCan be

  • And then define apreThe pointer starts pointingretAnd move backwards in turn to find the area to be reversedPrevious node, i.e.,1 nodesAnd then operate hisNext nodeRegion reversal

  • If the pre pointer points to the 2 nodes to be reversed, the region will turn into 4->3->2->5 after the inversion. At this point, the next of node 1 still points to 2 nodes, and the final result will turn into 1->2->5. What we need, however, is for next of node 1 to point to 4->3->2->5

  • The operation is performed at the position of 2 nodes, and the reverse step is similar to the previous one, except that a variable needs to be added to receive the reverse result, which also points to 2 nodes at the beginning

  • Invert the variable after the endnextPoint to the next one in the inversion regionNode 5

  • And then finally reverse this oneHead node pReturn to join the original linked list
  • Overall animation presentation

Code implementation

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}* /
var reverseBetween = function (head, left, right) {
  var ret = new ListNode(null, head)
  var cnt = right - left + 1 // The number of ranges to reverse
  var pre = ret
  while (--left) {
    pre = pre.next
  }
  pre.next = reverse(pre.next, cnt) If you reverse p directly, the first element of p still points to p, and the middle part of the inversion is skipped
  return ret.next
};

function reverse(head, cnt) {
  var p = null,
    q = ret = head
  while (cnt--) {
    head = head.next
    q.next = p
    p = q
    q = head
  }
  ret.next = q // The original head node is already pointing to NULL, and the next element after the inversion is connected
  return p
}
Copy the code

Difficult problems can be solved easily

25. Flip linked lists in groups of K

Analysis of the

  • If you don’t know how to reverse a linked list, this might make sense, but if you just get started, you might define a bunch of variables and end up getting tangled up, right
  • in92. Reverse linked list IIIf the number of remaining nodes is smaller than the number to be reversedkDo not turn
  • I started off by defining one againpreThe pointer starts pointinghead
  • Let’s define a pointerpreAt first pointretAt the end of each reversalkAfter 10 nodes, move backwardkStep until the end or the remaining number is less thank
  • Eventually returnret.nextCan be

Reference code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} k
 * @return {ListNode}* /
var reverseKGroup = function (head, k) {
  if (k === 1) return head
  var ret = new ListNode(0, head)
  var pre = ret

  while (1) {
    pre.next = reverse(pre.next, k)
    var n = k
    while (n-- && pre) { // Go backwards after reversing
      pre = pre.next
    }
    if(! pre)break // There is not enough time to get out of the loop
  }

  return ret.next
};

function reverse(head, k) {
  var p = ret = q = head,
    n = k
  while (--n && p) {
    p = p.next
  }
  if(! p)return head // The number of nodes to be reversed is less than k
  p = null
  while (k--) {
    head = head.next
    q.next = p
    p = q
    q = head
  }
  ret.next = q
  return p
}
Copy the code
  • If it’s not clear, you can draw it

— end —