专栏首页Gvoidy备份小站Python 单链表实现&基础函数

Python 单链表实现&基础函数

前两天面滴滴,被问到怎么判断两个链表是否相交,然后并不懂什么是单链表相交…就很尴尬。 赶紧复习一下单链表的知识。

单链表实现

class LNode:
    def __init__(self, elem, next_ = None):
        self.elem = elem
        self.next = next_

class LList:
    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head is None

    # 前端插入
    def prepend(self, elem):
        self._head = LNode(elem, self._head)

    # 删除头结点并返回
    def pop_first(self):
        if self.is_empty():
            raise LinkedListUnderFlow("in pop")
        e = self._head.elem
        self._head = self._head.next
        return e

    def append(self, elem):
        if self.is_empty():
            self._head = LNode(elem)
            return
        p = self._head
        while p.next:
            p = p.next
        p.next = LNode(elem)

    def pop(self):
        if self.is_empty():
            raise LinkedListUnderFlow("in pop")
        p = self._head
        if p.next is None:
            e = p.elem
            self._head = None
            return e

        # 用p.next.next做条件是因为把最后一个结点删除,需要找到倒数第二个结点
        while p.next.next is not None:
            p = p.next
        e = p.next.elem
        p.next = None
        return e

    def find(self, pred):
        p = self._head
        while p.next is not None:
            if pred(p.elem):
                # 构建生成器,找到了一个元素可以继续找下一个
                yield p.elem
            p = p.next


    def printall(self):
        p = self._head
        while p is not None:
            print(p.elem, end="")
            if p.next is not None:
                print(", ", end="")
            p = p.next

        # 换行,因为默认end参数为 "\n"
        # 等价 print("\n", end="")
        print("")

if __name__ == '__main__':
    my_list = LList()
    for i in range(10, 0, -1):
        my_list.prepend(i)
    my_list.printall()    # 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
    for i in range(11, 21):
        my_list.append(i)
    my_list.printall()
    print(my_list.pop())  # 20
    print(my_list.pop_first()) # 1
    my_list.printall()   # 2~19

    def find_odd(n):
        if n % 2 != 0:
            return n
    for i in my_list.find(find_odd):
        print(i)         # 1, 3, 5, 7, 9 ,...

补充一下print的参数

  • print(value, …, sep=’ ‘, end=’\n’, file=sys.stdout, flush=False)
  • sep: 多个参数之间的分隔字符串
  • end: print结束后的字符串
  • file: 输出到已打开的文件,注意,当文件关闭后才会保存
  • flush: 所有数据打印到控制台,立即“刷新”到实际控制台并保留待处理的打印缓冲区 可用于上面的文件操作,当文件未关闭时及时输出到控制台,参考Stack Overflow

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 常见设计模式 Python 实现

    单例模式,也叫单子模式,是一种常用的软件设计模式。在应用这个模式时,单例对象的类 “类 (计算机科学)”)必须保证只有一个实例存在。许多时候整个系统只需要拥有一...

    Ewdager
  • Python 中的魔术方法

    __new__(self): 创建并返回一个类的实例,而__init__只是将传入的参数来初始化该实例,一般不需要重载__new__方法除非希望控制类的创建。

    Ewdager
  • Python 中的上下文管理

    当我们执行语句块前需要一些准备动作,在执行完成之后又需要执行一些收尾动作。比如:文件读写后需要关闭,数据库读写完毕后需要关闭连接,资源加锁解锁等情况。对于这种情...

    Ewdager
  • PyQt 的动作组(QActionGroup)

    动作组(QActionGroup),是用于管理多个可选型动作(checkable QAction)的类,它可以保证组中所有的动作只要有一个“开”,则其他的所有动...

    用户6021899
  • [数据结构与算法] 链表的其他类型

    单链表是最简单的链表,单链表的一种变形就是循环单链表,其中最后一个结点的next域不用None,而是指向表的第一个结点,这样就形成了一种循环结构,所以叫循环单链...

    用户1622570
  • 打卡群2刷题总结1007——反转链表

    https://leetcode-cn.com/problems/reverse-linked-list/

    木又AI帮
  • LEETCODE - Linked List 题目思路汇总

    浏览了一下 Leetcode 上 Linked List 的题目,我把它分为 6 类: 调换顺序 删除 合并 环 变身 复制 做Leetcode还是要归类总结才...

    杨熹
  • 【python-leetcode206-翻转链表】反转链表

    输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

    绝命生
  • python pyqt5 信号连接、断开、发射

    from PyQt5.QtCore import QObject , pyqtSignal

    用户5760343
  • 基于Django的电子商务网站开发(连载25)

    购物车模块包括“购物车中所有商品的显示”“添加商品进入购物车”“删除购物车中某种商品”“删除购物车中所有的商品”和“修改购物车中某种商品的数量”。

    小老鼠

扫码关注云+社区

领取腾讯云代金券