【面试算法】链表反转

adam1q84 发布于2019-08-14 15:19 / 2185人阅读

摘要：今天来将一下面试中经常问到的一个问题链表反转。题目给一个单向链表，请编写一个函数，把链表反转，并把反转的链表返回。假设给的节点为双向链表反转函数如下

今天来将一下面试中经常问到的一个问题：链表反转。

【题目1】给一个单向链表，请编写一个函数，把链表反转，并把反转的链表返回。

假设给的节点为

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
        this.next = null;
    }
}

单向链表反转函数如下

public ListNode reverse1(ListNode head){
    ListNode prev = null;
    while(head != null){
        ListNode next = head.next; //获取下一个节点
        prev.next = head;          //更改上一个节点的指向  
        prev = head;               //上一个节点前进一位
        head = next;               //head节点前进一位
    }
    return prev;
}

【题目2】给一个双向链表，请编写一个函数，把链表反转，并把反转的链表返回。
假设给的节点为

class ListNode{
    int val;
    ListNode prev;
    ListNode next;
    public ListNode(int val){
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

双向链表反转函数如下

public ListNode reverse2(ListNode head){
    ListNode cur = null;
    while(head != null){
        cur = head;
        head = head.next;
        cur.next = cur.prev;
        cur.prev = head;
    }
    return cur;
}

GPU云服务器云服务器 python反转链表链表算法链表排序算法算法 c语言链表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65607.html

Java数据结构与算法——链表（面试）

摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。指针反转实现链表反转代码反转链表获取当前下下个元素测试代码部分用到了上篇文章数据结构与算法链表的代码段，请移步获取。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文是上篇文章Java数据结构与算法——链表的扩展篇，介绍链表的特点，使用场景、链表的性能分析以...

keke 2019-08-16 11:08 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
剑指offer系列——剑指 Offer 24. 反转链表（C语言）

摘要：假设反转对象节点为，反转指向的结点为，反转后指向的结点为首结点。当然也可以根据栈先进后出的特点，使用栈反转链表。 ⭐️前面的话⭐️ 大家好！博主开辟了一个新的专栏—...

weakish 2021-09-03 10:29 评论0 收藏0
反转链表

摘要：扯淡之前听说过面试反转链表的梗，也尝试着自己实现了一次，算是比较简单的问题。当然，前提是我们只持有头节点的引用，且称为，那么链表反转后的头节点，就是。扯淡之前听说过google面试反转链表的梗，也尝试着自己实现了一次，算是比较简单的问题。但在纸上手写代码的时候，思维就很乱，可能是隔的时间长忘记了，或者之前就跟本没有理清思路，所以被虐的很惨。这篇文章的目的就是梳理一下思路，加深印象。...

20171112 2019-08-14 15:16 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0