反转链表

题目

假设现在有一个链表，要实现链表反转

输入

1->2->3->4->5

输出

5->4->3->2->1

迭代实现思路

1. 定义指针 pev 初始值 null，curr 指向头指针 head，next 指向 curr.next

let curr = head;
let prev = null;
let next = null; // 记忆当前curr的next指针

2. 循环移动指针，判断当前 curr 指向是否为空，如果为空，则表示到达尾部，则停止循环

while (curr) {
  next = curr.next; // 由于下一步的 curr.next 指向了 prev，会无法获取到下一个 next，所以需要临时存储
  curr.next = prev;
  prev = curr;
  curr = next;
}

3. 当 curr 为空的时候，表示到了尾部，此时新的链表头部为 prev ，所以最终 return prev 即可

迭代算法代码

const reverseList = function(head) {
  let curr = head;
  let prev = null;
  let next = null;
  while (curr) {
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};

复杂度分析

时间复杂度：O(n)O(n)，其中 nn 是链表的长度。需要遍历链表一次。
空间复杂度：O(1)O(1)。

递归实现思路

1. 递归出口

if (!head || !head.next) {
  // head为空或者head下一个节点为空
  return head;
}

2. 拿到最后一节点（N），改变 next 指向，每次都返回该节点（N）

const newHead = reverseList(head.next); // 最后一个节点
// 反转
head.next.next = head; 
head.next = null;
return newHead;

这里返回 newHead 的原因是，是有一个节点的情况

递归算法代码

const reverseList = function(head) {
  if (!head || !head.next) {
      return head;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};

复杂度分析

时间复杂度：O(n)O(n)，其中 nn 是链表的长度。需要对链表的每个节点进行反转操作。
空间复杂度：O(n)O(n)，其中 nn 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 nn 层。