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

异名解题:反转链表

作者头像
异名
发布2020-06-08 18:57:38
发布2020-06-08 18:57:38
32600
代码可运行
举报
文章被收录于专栏:异名异名
运行总次数:0
代码可运行

反转一个单链表

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

解题思路

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

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

代码语言:javascript
代码运行次数:0
复制
/**
 * @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
代码运行次数:0
复制
/**
 * @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
代码运行次数:0
复制
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 条评论
热度
最新
推荐阅读
目录
  • 解题思路
    • 解法一 利用数组或者栈的存储结构
    • 解法二 双指针
    • 解法三 递归
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档