反转链表

2017-07-20

题目

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

输入

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

输出

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

迭代实现思路

1. 定义指针 pev 初始值 null,curr 指向头指针 headnext 指向 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 层。

标签: 算法

如果本文对您有所帮助,可以扫下面二维码给我支持,您的鼓励是我前进的动力!

微信

支付宝

目录

评论

*
*

正在加载验证码......

最新评论

  • 无评论
相关推荐
javascript之this详解(上)
1. 迷之 this 对于刚开始进行 JavaScript 编程的开发者来说,this 具有强大的...
javascript之this详解(下)
4. 构造函数调用 构造函数调用使用 new 关键词,后面跟随可带参数的对象表达式,例:new...
nginx常用配置
nginx是什么? Nginx是一个高性能的HTTP和反向代理服务器,也是一个IMAP/POP3/SMTP服务器。...