前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >异名解题:反转链表

异名解题:反转链表

作者头像
异名
发布2020-06-08 18:57:38
2960
发布2020-06-08 18:57:38
举报
文章被收录于专栏:异名异名

反转一个单链表

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

解题思路

解法一 利用数组或者栈的存储结构

在遍历的时候把节点存在数组里面,可以利用reverse方法,也可以利用数组存储特点做顺序记录

代码语言:javascript
复制
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList(head) {
    if (!head) return head;
    let list = [],tempNode = null, curNode = head;
    while (curNode) {
        tempNode = curNode.next || null
        curNode.next = list[list.length - 1] || null
        list.push(curNode);
        curNode = tempNode
    }
    return list[list.length-1]
};

解法二 双指针

构建两个指针prevcur分别存储上一个节点和当前节点,然后每次遍历的时候往后挪动两个指针,同时修改prevcurnext指向

代码语言:javascript
复制
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList(head) {
    let prev = null;
    let cur = head;
    let temp;
    while (cur) {
        temp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = temp;
    }
    return prev;
};

解法三 递归

这道题使用递归的方法理解会比较绕,结合递归的执行栈

① —-> ② —-> ③ —-> ④ —-> ⑤ —-> null

当前节点

返回节点

链表

⑤ --> ④ --> null

⑤ --> ④ --> ③ --> null

⑤ --> ④ --> ③ --> ② --> null

⑤ --> ④ --> ③ --> ② --> ① --> null

代码语言:javascript
复制
function reverseList(head) {
    if (!head || !head.next) return head;
    let nextLoopStartNode = reverseList(head.next);

    // 原本关系:headPrev = null, headNext = head.next
    // 反转操作:head.next = null, headNext.next = head
    head.next.next = head;
    head.next = null;

    return nextLoopStartNode;
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-05-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 异名 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解题思路
    • 解法一 利用数组或者栈的存储结构
      • 解法二 双指针
        • 解法三 递归
        相关产品与服务
        对象存储
        对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档