链表 206/24.反转一个单链表
力扣 206反转一个单链表/剑指offer 24
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
//Definition for singly - linked list.
function ListNode(val) {
this.val = val;
this.next = null;
}
【小声BB】：虽然递归听起来比较高级，但是其实这三种算法都是一个时间复杂度的…所以能解决问题的算法就是好算法
- 1.自己写的算法：
时间复杂度：O(n)，空间复杂度：xx
思想：用数组存储反向链表的值，然后再从链表头到尾重新赋值
var reverseList = function (head) {
// 存储第一个节点，用于获取节点值 arr
let pNode = head;
let arr = [];
while (pNode !== null ) {
arr.unshift(pNode.val);
pNode = pNode.next
};
// 重新赋值第一个节点，作为结果的 head
let first = head;
for(let i=0; i<arr.length; i++) {
head.val = arr[i];
head = head.next;
}
return first
};
- 2.官方方法一：
假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。
通过三个节点迭代： prev 前一个节点，current 当前节点，next 下一个节点
时间复杂度：O(n)，空间复杂度：xx
var reverseList = function (head) {
let prev = null;
let current = head;
while (current != null) {
// 在更改引用之前，还需要另一个指针来存储原始的下一个节点
let next = current.next;
// 当前节点的 next 指针改为指向前一个元素（实现反向）
current.next = prev;
// （存的就是当前反向后的正确的节点）由于节点没有引用其上一个节点，事先存储其前一个元素
prev = current;
// 往后走到原始的下一个节点
current = next;
}
// 此时，由于 current 已经因为 while 循环走到了下一个 null 节点，所以返回 prev
return prev
}
如下是上面算法的拆解版本，还是上面版本好，下面的算法可略过不看：
时间复杂度：O(n)，空间复杂度：xx
var reverseList = function (head) {
// head 只有一个节点
if (head === null || head.next === null) {
return head
}
let second = head.next;
// head 只有两个节点
if (head.next.next === null) {
second.next = head;
head.next = null;
return second;
}
let third = second.next;
// 大于等于3个节点
// tail 节点
head.next = null;
while(third !== null) {
second.next = head;
// 往后走
head = second;
second = third;
third = third.next;
}
second.next = head;
// 返回头节点
return second
}
- 3.官方方法二：递归
递归版本稍微复杂一些，其关键在于反向工作。
时间复杂度：O(n)，空间复杂度：xx
假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？
假设列表为： n1->… -> n{k-1} -> n{k} -> n{k+1} -> … -> n{m} -> Ø
若从节点 n{k+1}到 n{m}已经被反转，而我们正处于 n{k}。
n{1}-> … -> n{k-1} -> n{k} -> n{k+1} <-… <-n{m}
我们希望 n{k+1} 的下一个节点指向 n{k} 。
所以，n{k}.next.next = n{k}。
边界条件（退出循环条件）： n{1}的下一个必须指向 Ø 。
如果使用大小为 2 的链表测试代码，则可能会捕获此错误。
var reverseList = function (head) {
if (head == null || head.next == null) return head;
var p = reverseList(head.next);
// 为了便于自己理解，假设输入的是 1->2->3->4->5:
// 第一次返回的递归执行到这儿时：p = 5 -> null；head = 4->5（head由于闭包，每次都会比p早一个节点）
head.next.next = head; // 5->4->5->4... 循环
head.next = null; // 4 -> null
// 返回 p 之前，可以看到：p = 5 -> 4 -> null
return p;
}