链表相关——Python实现
一、链表的创建及数据插入
示例代码：
#1.定义一个结点类
class ListNode():def __init__(self,x,next=None):self.val=xself.next=next
#2.定义单链表
class LinkList():#2.1 创建一个头指针为空的链表def __init__(self,head=None):self.head=None#2.2 将数据插入链表(最后返回链表的头指针)def initList(self,data):#2.3 创建头结点self.head=ListNode(data[0])r=self.headp=self.head#2.4 逐个为data内的数据创建结点，建立链表for i in data[1:]:node=ListNode(i)p.next=nodep=p.nextreturn rdef printList(self,head):if not head:return []node=headwhile node:print(node.val,end='\t')node=node.nextprint()if __name__ == '__main__':l=LinkList()tup1=(1,2,3,4,5)lst1=[6,7,8,9,10]l1=l.initList(tup1)l2=l.initList(lst1)l.printList(l1)l.printList(l2)运行结果：
二、链表反转
#集合添加元素
# s={1,2,3} 1->2->3 3->2->1
# s.add(4)
# print(s)
class ListNode():def __init__(self,x):self.val=xself.next=None
class Solution():def ReverseList(self,head:ListNode)->ListNode:#处理空链表if not head:return Nonecur=headpre=Nonewhile cur:#断开链表，要记录后续一个temp=cur.next#当前的next指向前一个cur.next=prepre=curcur=tempreturn pre
三、合并两个有序链表
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
#
class Solution:def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:# write code herecur0=cur=ListNode(12)while pHead1 and pHead2:if pHead1.val<pHead2.val:cur.next=pHead1pHead1=pHead1.nextcur=cur.nextelse:cur.next=pHead2pHead2=pHead2.nextcur=cur.nextcur.next=pHead1 or pHead2return cur0.next