当前播放: 06 | 面试题:反转一个单链表&判断链表是否有环
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
课程目录
第一章:课程综述 (4讲)
01 | 合格程序员的第一步:算法与数据结构
免费
02 | 如何事半功倍地学习算法与数据结构
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算法题目练习
免费
第二章:理论讲解+面试题实战 (53讲)
05 | 理论讲解:数组&链表
免费
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
12 | 面试题:返回滑动窗口中的最大值
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二叉搜索树
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索树的最近公共祖先
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时机
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最小深度
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方根的函数
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词搜索问题
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&比特位计数问题
42 | 面试题:N皇后问题的另一种解法
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径和
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友圈(上)
54 | 面试题:岛屿的个数&朋友圈(下)
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
第三章:课程总结 (5讲)
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 最后的一些经验分享
06 | 面试题:反转一个单链表&判断链表是否有环

06 | 面试题:反转一个单链表&判断链表是否有环

覃超
Sophon Tech创始人,前Facebook工程师,卡内基梅隆大学计算机硕士
62讲 62课时·约600分钟19895
单独订阅¥129
2人成团¥99
93
本节摘要

课件获取

关注“极客时间”微信公众号,在后台回复“算法试看”,即可获取试看课程的 PDF 课件。

反转一个单链表:

两两交换链表中的节点

判断链表是否有环:

环形链表

展开
登录 后留言

精选留言(122)

  • fExperience
    看到好多小伙伴在问,我来尝试解释一下“链表交换相邻元素”中 self 是怎么回事。
    ------
    1. 首先看到最后 return self.next ,可以看到作者是想把 self 当做链表的头指针使用的(注意:头指针 pHead 与传入的参数 head 是不同的,head 是第一个结点,而 pHead.next == next )。用头指针有什么好处呢?因为我们让头指针的 next 域(pHead.next)永远指向第一个结点,就是避免最后返回的时候找不到第一个结点了。

    2. 那么作者为什么可以 pre, pre.next = self, head 这样写呢?因为 self 是这个类的一个对象,所以在类定义的时候可以在任何地方,给 self 增加新的属性。相信大家都知道在 __init__(self, attr) 里面可以定义通过 self.myattr = attr 来定义一个 myattr 属性。其实这个语句写在任意一个类的方法里都可以,所以在原文 swapPairs() 里面当然也可以定义新的属性。所以这行代码应该理解为,pre 指向 self(虽然 self 不是一个 ListNode 类型的对象,但它只要有一个 next 就可以了),同时为 pre(同时也是为 self,它们是一样的现在)增加一个 next 属性,这个 next 属性指向第一个结点 head。

    3. 明白上面之后,这里就好办了。在第一次 while 循环的时候,pre.next 被赋值为 b(也就是原来第二个结点,转换为变成了第一个,也就成为了新链表的第一个结点。如果原来是[1,2,3,4],那么现在就是[2,1,3,4],这个 self.next 就是指向 2 这个结点)。所以最后只要返回 self.next 就得到了答案。
    ------

    其实换个写法大家就好理解很多了:
    pHead = ListNode(None)
    pre, pre.next = pHead, head
    也就是说不用 self 也可以,只是原作者秀了一把小技巧而已。

    长篇大论,感谢阅读,如若有误,强烈欢迎指出。
    2018-11-08
    2
    55
  • 空指针
    之前一直以为像这样的语句 cur.next, prev, cur = prev, cur, cur.next 是一个一个分别按先后执行的,这次研究了一下,发现原来是先算好等号右边的所有值,然后一次性赋给左边...

    作者回复: 对的! 一次性赋值

    2018-10-19
    2
    34
  • 探索无止境
    第二道题两两交换,slef是什么意思?我觉得这点录制得很随意,难道要我们再学一个python,然后再来学习这个算法视频教程?我觉得要制作一个好的教程,必须是给读者建立一个梯度,而不是用一个读者不懂的东西来讲解另一个不懂的东西,然后只是直接晒出代码
    2019-02-21
    26
  • Geek_d7a810
    看完整个课程,发现作者基本都是python实现的代码,python语言本身很多的数据结构和语法糖,后面偶尔看见有用java实现的题目,也是一些简单的题。这点有点小失望。
    2018-12-20
    24
  • liyoucheng
    老师,
    1. 题目都不讲完,要自己去弄得话,那还不如百度搜索看看那不就得了,那我还来这看啥呢,肯定是想听听老师是怎么讲的呢
    2. 说好的有c语言、python、java版本,暂时只看到python,并没看到其它两种,这不是有点骗人不

    作者回复: 1 有些题目自己练习;
    2 最好让自己对语言中性,主要看程序的逻辑。

    2018-10-13
    18
  • Wobum
    链表两两交换的那个代码中,第一行代码中的 self 看不是很懂,老师可以详细解答一下么,我对 Python 类中的 self 是干什么的都不是很了解,或者给我们一些资料链接什么的,谢谢老师了。
    2018-10-12
    16
  • slinv
    不是恨懂Python一次性赋值的同学注意了。像@空指针的留言一样,在
    current.next, prev, current = prev, current, current.next
    这句代码中是等号右边的值全部都保存了才会一次性赋值给等号左边的变量,如果把这一行分开写成
    current.next = prev
    prev = current
    current = current.next
    是不行的。所以为什么其他语言里面要先有一个tempNext来记录cur.next。
    这个在Python里面叫sequence unpacking,不是按顺序从左到右赋值的。
    2018-11-04
    15
  • 子青
    java没有python那么多语法糖,写起来肯定不一样。老师也说链表主要不是思维,是实现能力,所以还是希望有java、c版本的代码。

    作者回复: 后续题目里会随机挑选其他不同语言。

    我们题目的python代码里没有用什么特殊的语法,就是正常的逻辑语句

    2018-10-14
    12
  • 默默
    我觉着第一个问题讲的有点不负责任,一句思路很简单就完了,然后给出的代码完全是靠python的语法糖来取巧的。虽然说解决问题是最主要的,但是既然讲算法,那么不应该脱离语言本身的特性,使用一些编程语言普遍具有的特性来表现逻辑吗?
    2019-06-22
    10
  • Wilson
    判断链表是否有环,判断最后节点是否为null的方法应该不行。如果有环他就会无限圆环下去。所以觉得这个不行。副自己写的java代码实现老师说得三个示例
    /**
         * 反转一个单链表。
         * <p>
         * 示例:
         * <p>
         * 输入: 1->2->3->4->5->NULL
         * 输出: 5->4->3->2->1->NULL
         *
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head) {
            if (head == null) {
                return head;
            }
            ListNode pre = head;
            ListNode cur = head.next;
            ListNode temp;
            while (cur != null) {
                temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            head.next = null;
            return pre;
        }
    /**
         * 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。如:给定 1->2->3->4, 你应该返回 2->1->4->3.
         *
         * @param head
         * @return
         */
        public ListNode swapPairs(ListNode head) {
            ListNode dump = new ListNode(0);
            dump.next = head;
            head = dump;
            while (head.next != null
                    && head.next.next != null) {
                ListNode n1 = head.next;
                ListNode n2 = head.next.next;
                head.next = n2;
                n1.next = n2.next;
                n2.next = n1;
                head = n1;

            }
            return dump.next;
        }
    /**
         * 判断是否环
         *
         * @param head
         * @return
         */
        public boolean hasCycle(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && slow != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    return true;
                }
            }
            return false;
        }

    作者回复: 👍🏻👍🏻👍🏻 good

    2018-10-16
    1
    8
  • Sun0010
    cur.next ,pre,cur = pre ,cur,cur.next 这个没看懂,怎么办

    作者回复: python里的多变量赋值是一次性完成的操作。

    2018-10-24
    1
    5
  • ttttt
    其实明白两点就好理解了:
    1、节点1 = 节点2 是赋值,即把节点2的data,和指向同时赋值给节点1。同时改变值和next指向。
    2、节点.next = *** 是指向,只改变next指向。
    这样就很好理解了。
    2019-08-26
    3
  • Heimerdinger
    请问老师 pre, pre.next = self, head
    这一句是什么意思? 视频中为什么可以返回self.next呢?
    2018-11-06
    3
  • 15652790052
    if slow is fast or slow is fast.next :
      return True
      slow = slow.next
      fast = fast.next.next

    这样可以更好理解 更快找到
    进入环以后 快指针追赶慢指针, 对快指针走过的节点都和慢指针比较 只要快指针追上慢指针就是有环
    2019-01-03
    2
  • Quantum
    python递归和非递归的实现:

    递归实现:
    # Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None

    class Solution(object):
        def reverseList(self, head, prev=None):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not head:
                return prev
            head.next, prev, head = prev, head, head.next
            return self.reverseList(head, prev)


    非递归实现:
    # Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None

    class Solution(object):
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            prev = None
            while head:
                head.next, prev, head = prev, head, head.next
            return prev
    2018-10-20
    2
  • liyoucheng
    老师,不是有C语言实现的提供吗?
    struct ListNode* swapPairs(struct ListNode* head) {
        struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
        //头节点
        struct ListNode *pre = dummy;
        pre->next = head;
        
        while (pre->next != NULL && pre->next->next != NULL) {
            struct ListNode *a = pre->next;
            struct ListNode *b = a->next;
            
            struct ListNode *temp = b->next;
            pre->next = b;
            b->next = a;
            a->next = temp;
            pre = a;
        }
        
        return dummy->next;
    }

    作者回复: 对的。可以使用你最擅长的语言练习一下。

    2018-10-11
    2
  • 克里斯
    public ListNode reverseList(ListNode head) {
            return reverseList(head,null);
        }
        public ListNode reverseList(ListNode cur, ListNode pre) {
            if (cur == null) {
                return pre;
            }
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            return reverseList(cur, pre);
        }
    2019-06-17
    1
  • 克里斯
    为啥我感觉反转链表一点都不简单😥。
    这里改变一个节点的next会涉及到两个指针pre,cur.
    但是在java里还需要一个指针来保存temp=cur.next.

    因为反转链表的过程中会断开,形成两个链表,一个排好序的,一个没有排序的。因此必须要有一个指针记录未排序的链表。
    2019-06-17
    1
  • 狼烟
    现在有java版本了吗
    2019-04-17
    1
  • bread22
    为什么 下面两个写法结果不一样? 第一个会出错
    第一个在第一次迭代后curr.next就变成None了,感觉还是顺序赋值,对吗?


                curr, prev, curr.next = curr.next, curr, prev
                curr.next, curr, prev = prev, curr.next, curr

    作者回复: 自己针对多值赋值研究下可能印象更加深刻。

    2019-04-04
    1
收起评论
看过的人还看
左耳听风

陈皓  网名“左耳朵耗子”,资深技术专家,骨灰级程序员

108讲 | 41730 人已学习

拼团 ¥249 原价 ¥299
Java核心技术面试精讲

杨晓峰  前Oracle首席工程师

43讲 | 44337 人已学习

拼团 ¥79 原价 ¥99
趣谈网络协议

刘超  网易研究院云计算技术部首席架构师

51讲 | 41223 人已学习

限时 ¥79 原价 ¥99
数据结构与算法之美

王争  前Google工程师

79讲 | 75247 人已学习

拼团 ¥79 原价 ¥99