PRE

This is the 7th day of my participation in Gwen Challenge

206. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Analysis of the

The special thing about a single necklace list is that the information for the next element will disappear if you change the current index. Simple brute force solutions can try using arrays to store data temporarily while you process it

Now, if you think about how to optimize the time layer you’re going to iterate over all the elements anyway, so it’s going to be O(N) at the minimum, but you can optimize the space layer and the array violence solution that you’re using is O(N) in space and in fact, The key to list inversion is how do you transform the list without losing the nodes that come after you and to do that you don’t have to keep all the lists, you just temporarily store the last one and the next one and then you get O(1) in space

implementation

The iteration

/** * 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) {
  // The key to list inversion is how to transform the nodes without losing them
  // Use more Pointers for temporary saving
  let prev = null
  let curr = head
  while(curr) {
    // Save before converting
    const next = curr.next
    curr.next = prev
    
    prev = curr
    curr = next
  }
  return prev
};
Copy the code

recursive

/** * 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) {
  return reverse(null, head)

  function reverse(prev, curr) {
    if(! curr)return prev
    const next = curr.next
    curr.next = prev

    // return reverse(prev = curr, curr = next)
    return reverse(curr, next)
  }
};
Copy the code

Note the use of recursion because of the introduction of a call stack to temporarily store the PREV, which is actually O(N) complexity

thinking

In writing, the same format is deliberately used, and you can see a lot of similarities between iterative and recursive writing

The process can be made clearer by drawing pictures

END

Welcome to SedationH

Try to use JS more clear analysis and implementation of the algorithm topic ~