LeetCode 206. 反转链表（迭代+递归）

Hi，大家好，我是小庄。

今天打卡的算法题是 —— LeetCode 206.反转链表

该题将采用「迭代法」和「递归法」分别实现

话不多说，一起来学习吧～

一、Leetcode题目

1、题目地址

点击查看Leetcode题目

2、具体题目

二、实现代码

1、思路：迭代法；

（1）具体代码

/**
 * 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}
 */
/*
    思路：迭代法；
    时间复杂度：O(n)；
    空间复杂度：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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

（2）运行结果

2、方法：递归法；

（1）具体代码

/**
 * 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}
 */
/*
    思路：递归法实现；
    时间复杂度：O(n);
    空间复杂度：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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

（2）运行结果

3、补充部分

注：以下为手动构建完整链表，并采用迭代法实现。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

三、讲解视频

点击查看B站讲解视频

四、补充部分

关注公众号：【深漂程序员小庄】：
内含丰富的学习资源和面试经验（不限前端、java），还有学习交流群可加，并且还有各大厂大佬可一起交流学习，一起进步～添加小庄微信，回复【加群】，可加入互联网技术交流群。

本文由mdnice多平台发布