Hi，大家好，我是小庄。
今天打卡的算法题是 —— LeetCode 206.反转链表
该题将采用「迭代法」和「递归法」分别实现
话不多说，一起来学习吧～
一、Leetcode题目
1、题目地址
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;
};
<br />
（2）运行结果
<br />
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;
};
<br />
（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
三、讲解视频
四、补充部分
关注公众号：【深漂程序员小庄】：
内含丰富的学习资源和面试经验（不限前端、java），还有学习交流群可加，并且还有各大厂大佬可一起交流学习，一起进步～添加小庄微信，回复【加群】，可加入互联网技术交流群。
本文由mdnice多平台发布
