欢迎关注微信公众号:简说Python 关注后回复:1024,可以领取精选编程学习电子书籍。
这两天和几个朋友组了个互相督促学习群,想着督促一下自己学习,也督促自己的原创输出,其实很多时候都是懒,真不是没有东西可以写了,这不,我在我的免费知识星球简说编程里开了个新的标签日常编程问题,后面我会把自己学习工作中遇到的一些问题和解决方法记录到里面,有些可以扩展的点,我会写到微信公众号里。 我定的目标是:
我简单写了个规则,大家说可以,然后,我们就开始吧,我习惯把该做的事情提前一天做(如果有时间的话)。
今天给大家分享的书籍《Python程序员面试算法宝典》第一章链表的所有小节后的引申部分。
如果你是第一次看,也许,你可以看看本系列下面的文章: Smaller And Smarter Python数据结构:链表逆转 Smaller And Smarter Python数据结构:删除无序链表重复结点 Smaller And Smarter Python数据结构:链表相加 Smaller And Smarter Python数据结构:链表进行重新排序 Smaller And Smarter Python数据结构:链表倒数第K个元素+检测单链表环 Smaller And Smarter Python数据结构:翻转链表相邻结点 Smaller And Smarter Python数据结构:翻转链表k个相邻结点 Smaller And Smarter Python数据结构:合并两个有序链表 Smaller And Smarter Python数据结构:单链表删除给定结点,只给该结点+判断&找出交叉结点 Smaller And Smarter Python数据结构:展开链接链表(超级有趣的链表)
首先我们写好链表的基本操作,在a_0_base.py文件中,目前包含对链表的定义类,初始化函数,遍历函数。
# -*- coding: utf-8 -*- """ @author = 老表 @date = 2019-10-19 @个人微信公众号 : 简说Python """ import random # 链表数据结构定义 class ListNode: def __init__(self, x): self.data = x self.next = None # 特殊链表结构定义 class SNode: def __init__(self, x): self.data = x self.right = None self.next = None class ListOperation: # 根据链表数据初始化链表,带头结点 @staticmethod def init_list(n_list): # 初始化一个头指针 head = ListNode("head") cur = head for i in n_list: node = ListNode(i) cur.next = node cur = node # 相当于 cur = cur.next,后移 return head # 根据链表数据初始化链表,不带头结点 @staticmethod def init_list_n(n_list): head = ListNode(n_list[0]) cur = head for i in range(1, len(n_list)): node = ListNode(n_list[i]) cur.next = node cur = node # 相当于 cur = cur.next,后移 return head # 根据链表数据初始化一个有环的链表 @staticmethod def init_ring_list(n_list): # 初始化一个头指针 head = ListNode("head") cur = head for i in n_list: node = ListNode(i) cur.next = node cur = node # 相当于 cur = cur.next,后移 cur.next = head.next.next.next.next # 随意的,让最后一个结点指向第四个结点 return head # 遍历链表,不带头结点 @staticmethod def ergodic_list_n(head): # print(head.data) cur = head while cur: print(cur.data, end=" ") cur = cur.next # 遍历链表 @staticmethod def ergodic_list(head): # print(head.data) cur = head.next while cur: print(cur.data, end=" ") cur = cur.next # 获取链表长度 @staticmethod def get_len_list(head): cur = head.next len_list = 0 while cur: len_list = len_list + 1 cur = cur.next return len_list # 随机获取一个结点 @staticmethod def get_random_node(head): cur = head.next i = 0 len_list = ListOperation.get_len_list(head) while cur.next: if i == random.randint(0, len_list-1): break cur = cur.next return cur # 制作一个随机交叉链表 @staticmethod def get_random_link(n_list, head1): p = ListOperation.get_random_node(head1) # 获取一个链表1的随机结点 # 初始化一个头指针 head = ListNode("head") cur = head for i in n_list: node = ListNode(i) cur.next = node cur = node # 相当于 cur = cur.next,后移 cur.next = p # 将链表1的从p结点开始的后半部分,添加到当前链表后 # 当前链表与链表1相交 return head # 返回新创建的链表头结点 # 初始化特殊链表 @staticmethod def init_snode(right_data, down_data): # 初始化一个头指针 head = SNode("head") cur = head for i in range(len(right_data)): right_node = SNode(right_data[i]) # right,主干 right_node.next = ListOperation.init_list(down_data[i]).next # down cur.right = right_node cur = right_node # 相当于 cur = cur.next,后移 return head # 遍历特殊链表 @staticmethod def ergodic_s_list(head): right_node = head.right while right_node: print(right_node.data, end=" ") down_node = right_node.next while down_node: print(down_node.data, end=" ") down_node = down_node.next print() print("*************************") right_node = right_node.right开始程序前需提前导入前面写好的链表基本操作包和结点数据结构,在Linked_list的a_0_base.py中。
from Linked_list.a_0_base import ListOperationSmaller And Smarter Python数据结构:链表逆转
""" 第一小节引申: 1、对不带头结点的单链表进行逆序 2、从尾到头输出链表结点值 """2、对不带头结点单链表从尾到头输出链表结点值
# 2、对不带头结点单链表从尾到头输出链表结点值 def link_reverse_print(link_node): if not link_node: return link_node # 链表只有一个结点,或者为空链表,或者递归找到尾结点 cur_node = link_node head_node = link_reverse_print(cur_node.next) # 递归,往后遍历,到尾结点然后开始向前回溯 print(cur_node.data, end=" ") # 打印结点值 return head_node # 返回前一个结点Smaller And Smarter Python数据结构:删除无序链表重复结点
""" 第二小节引申: 如何从有序链表中移除重复项(带头结点链表) """Smaller And Smarter Python数据结构:链表进行重新排序
""" 第四小节引申: 如何查找链表中间结点(带头结点链表) """Smaller And Smarter Python数据结构:链表倒数第K个元素+检测单链表环
""" 第五小节引申: 如何将单链表向右旋转k个位置 要求解读:把链表倒数的k个元素移到链表开头,就表示旋转了k个位置 输入:-> 1 -> 2 -> 3 -> 4 -> 5 输入:k = 2 输出:-> 4 -> 5 -> 1 -> 2 -> 3 """Smaller And Smarter Python数据结构:链表倒数第K个元素+检测单链表环
""" 第六小节引申: 如果链表存在环,如何找到环入口 """Smaller And Smarter Python数据结构:单链表删除给定结点,只给该结点+判断&找出交叉结点
""" 第十小节引申: 只给定单链表中的某个结点p(非空结点),如何在p前面插入一个结点 要求解读:和本节的只给定一个结点然后删除该结点遇到的问题是一样的, 要删除或者插入一个结点,必须得知道该结点的前驱结点,但现在只有一 个结点,所以我们只能采用后插然后交换结点数据域。 原链表:-> 1 -> 2 -> 3 -> 4 -> 5 输入:2(表示链表第二个结点) 输入:10(表示待插入结点) 输出:-> 1 -> 10 -> 2 -> 3 -> 4 -> 5 """Smaller And Smarter Python数据结构:单链表删除给定结点,只给该结点+判断&找出交叉结点
""" 第十一小节引申: 如何单链表有环,如何判断两个链表是否相交 要求解读:首先我们要理解的是,单链表有环的话,环一定末尾, 因为单链表只有一个指向next,所以一个有环的单链表和一个没 环的单链表肯定不相交;两个有环的单链表才有可能相交,而且 两个链表环肯定是一样的(不可能在环后相交,有环的单链表实 际可以把环看作一个尾结点),实际上我们只需找出一个链表的 环上的一个结点,然后判断该结点在不在另一个链表即可。 注意:如果是找一个非环入口的结点,则当两链表不相交,判断该 环结点在不在另一个链表(带环)内时,会陷入死循环;所以最好 的办法是找出两个链表的环结点,如果相同,则说明相交,否则, 不相交。(也可以找出一个环结点,然后遍历另一个链表,看看该 环结点是否在另一个链表) 输入:-> 1 -> 2 -> 3 -> 4 -> 5 输入:k = 2 输出:-> 4 -> 5 -> 1 -> 2 -> 3 """到此链表已经结束了,有时间,我会把数据结构中链表操作和解题技巧归纳总结,发布到知识星球:简说编程。
本文代码思路部分来自书籍《Python程序员面试宝典》,书中部分代码有问题或未提供代码,文中已经修改过了,并添加上了丰厚的注释,方便大家学习,后面我会把所有内容开源放到Github上,包括代码,思路,算法图解(手绘或者电脑画),时间充裕的话,会录制视频。 希望大家多多支持。
大家好,我是老表 觉得本文不错的话,转发、留言、点赞,是对我最大的支持。
欢迎关注微信公众号:简说Python 关注后回复:1024,可以领取精选编程学习电子书籍。