1 """ 2 linklist.py 3 单链表的构建与功能操作 4 重点代码 5 """ 6 7 class Node: 8 """ 9 思路：将自定义的类视为节点的生成类， 10 实例对象中包含数据的部分和下一个节点的next 11 """ 12 def __init__(self,val,next = None): 13 self.val = val # 有用数据 14 self.next = next # 循环下一个节点的关系 15 16 # node1 = Node(1) 17 # node2 = Node(2,node1) 18 # node3 = Node(3,node2) 19 20 class LinkList: 21 """ 22 思路：单链表类，生成对象可以进行增删改查操作 23 具体操作通过调用具体方法完成 24 """ 25 def __init__(self): 26 """ 27 初始化链表，标记一个链表的开端，以便于获取后续的值 28 """ 29 self.head = Node(None) # 定义开端 30 # 通过为list_为链表添加一组节点 31 def init_list(self,list_): 32 p = self.head # p 作为移动变量 33 for item in list_: 34 p.next = Node(item) 35 p = p.next 36 37 # 遍历链表 38 def show(self): 39 p = self.head.next # 第一个有限节点 40 while p is not None: 41 print(p.val) 42 p = p.next # p 向后移动 43 44 # 判断链表为空 45 def is_empty(self): 46 if self.head.next is None: 47 return True 48 else: 49 return False 50 51 # 清空链表 断开head 52 def clear_linklist(self): 53 self.head.next = None 54 55 # 增加节点 56 def add_node(self): 57 """ 链表不在尾部增加，因为要遍历到尾部 58 59 """ 60 pass 61 62 # 尾部插入节点,比列表插入慢 63 def insert_end(self,val): 64 p = self.head 65 while p.next is not None: 66 p = p.next 67 p.next = Node(val) 68 69 # 头部插入，速度快 70 def insert_head(self,val): 71 node = Node(val) # 1.新建节点 72 node.next = self.head.next # 新节点指向原第二节点 73 self.head.next = node # head 节点 74 75 # 指定插入 难度*** 76 def insert_appoint(self,index,val): 77 # 注意循环的临界问题,和头部插入类似 78 p = self.head 79 for i in range(index): 80 # 如果index 值过大，退出循环 81 if p.next is None: 82 break 83 p = p.next 84 node = Node(val) 85 node.next = p.next 86 p.next = node 87 88 # 删除节点 效率比列表快，不需要内存的移动 89 def delete_node(self,x): 90 p = self.head 91 # 结束循环，必定条件有假,先判断是不是none,短路原则 92 while p.next and p.next.val != x: 93 p = p.next 94 if p.next is None: 95 raise ValueError("x not in linklist") 96 else: 97 p.next = p.next.next 98 99 # 获取某个节点的值,传入节点位置， 100 def get_node(self,index): 101 if index < 0: # 判断索引值是否有误 102 raise IndexError("index out of range") 103 p = self.head.next 104 for i in range(index): 105 if p.next is None: 106 raise IndexError("list index out of range") 107 p = p.next 108 return p.val 109 110 # 将第二个列表合并到第一个列表中，正序排列 111 def merge_linklist(list1, list2): 112 """ 113 p 指向l1-head,q 指向l2-元素2，p.next值和q比较 114 如果比q小，p向后移动,此时p.next为3，大于2，令中间变量 115 指向p.next,让p指向q,让q等于中间变量，p向后走指向2，重复 116 上述操作，不用开辟第三个链表 117 118 :param l1: 119 :param l2: 120 :return: 121 """ 122 p = list1.head # p指向l1头 123 q = list2.head.next # q指向l2的元素2 124 while p.next is not None: 125 if p.next.val < q.val: 126 p = p.next 127 else: 128 # 前两必须标记，后两可以不按顺序 129 tmp = p.next 130 p.next = q 131 p = p.next 132 q = tmp 133 p.next = q 134 135 #------测试代码------- 136 #if __name__ == "__main__": 137 # l = LinkList() 138 # # l.head.next = Node(1) 139 # # print(l.head.next.val) # 1 140 # l.init_list([1,2,3,4,5]) 141 # l.show()