下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 06 | 面试题:反转一个单链表&判断链表是否有环
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18804
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
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 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享
本节摘要

课件获取

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

反转一个单链表:

两两交换链表中的节点

判断链表是否有环:

环形链表

每 k 个节点一组翻转链表

展开

精选留言(118)

  • 2018-11-08
    看到好多小伙伴在问,我来尝试解释一下“链表交换相邻元素”中 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 也可以,只是原作者秀了一把小技巧而已。

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

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

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

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

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

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

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

    11
  • 2019-06-22
    我觉着第一个问题讲的有点不负责任,一句思路很简单就完了,然后给出的代码完全是靠python的语法糖来取巧的。虽然说解决问题是最主要的,但是既然讲算法,那么不应该脱离语言本身的特性,使用一些编程语言普遍具有的特性来表现逻辑吗?
    8
  • 2018-10-16
    判断链表是否有环,判断最后节点是否为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

    1
    7
  • 2018-10-24
    cur.next ,pre,cur = pre ,cur,cur.next 这个没看懂,怎么办

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

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

    这样可以更好理解 更快找到
    进入环以后 快指针追赶慢指针, 对快指针走过的节点都和慢指针比较 只要快指针追上慢指针就是有环
    展开
    2
  • 2018-10-20
    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
    展开
    2
  • 2018-10-11
    老师,不是有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;
    }
    展开

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

    2
  • 2019-06-17
    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);
        }
    展开
    1
  • 2019-06-17
    为啥我感觉反转链表一点都不简单😥。
    这里改变一个节点的next会涉及到两个指针pre,cur.
    但是在java里还需要一个指针来保存temp=cur.next.

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


                curr, prev, curr.next = curr.next, curr, prev
                curr.next, curr, prev = prev, curr.next, curr
    展开

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

    1