LeetCode 206. Reverse linked list (iteration + recursion)

Hi, Hello everyone , I am Xiaozhuang .

Today's algorithm for punching cards is —— LeetCode 206. Reverse a linked list

This question will use 「 Iterative method 」 and 「 Recursive method 」 respectively

Don't talk much , Let's study together ～

One 、Leetcode subject

1、 Title address

Click to see Leetcode subject

2、 Specific topic

Two 、 Implementation code

1、 Ideas ： Iterative method ;

（1） Specific 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
 * @return {ListNode}
 */
/*
     Ideas ： Iterative method ;
     Time complexity ：O(n);
     Spatial complexity ：O(1)
 */
var reverseList = function(head) {
    let pre = null;
    let cur = head;
    let next = head;
    while(cur !== null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};

（2） Running results

2、 Method ： Recursive method ;

（1） Specific 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
 * @return {ListNode}
 */
/*
     Ideas ： Recursive method to achieve ;
     Time complexity ：O(n);
     Spatial complexity ：O(n);
 */
var reverseList = function(head) {
    if(head === null || head.next === null) {
        return head;
    }
    let res = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return res;
};

（2） Running results

3、 The supplementary part

notes ： Here is how to build a complete linked list manually , And the iterative method is used to realize .

function ListNode(val) {
  this.val = val;
  this.next = null;
}

function createList(n) {
  let head = null;
  while(n) {
    let tempNode = new ListNode(n);
    tempNode.next = head;
    head = tempNode;
    n--;
  }
  return head;
}

let head = createList(3);
console.log(head);//1->2->3

function getReverseList(head) {
  let pre = null;
  let cur = head;
  let next = head;
  while(cur !== null) {
      next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
  }
  return pre;
}
let res = getReverseList(head);
console.log(res);//3->2->1

3、 ... and 、 Explain the video

Click to see B The station explains the video

Four 、 The supplementary part

Official account ：【 Deep drift programmer Xiaozhuang 】： It contains rich learning resources and interview experience （ Not limited to the front end 、java）, There are also learning exchange groups to add , In addition, there are leaders of major factories who can exchange and learn together , Progress together ～ Add Xiaozhuang wechat , reply 【 Add group 】, You can join the Internet technology exchange group .