+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-04(16)

2020-05(22)

2020-06(45)

2020-07(31)

2020-08(32)

牛客网剑指Offer-JZ16.合并两个排序的链表

发布于2021-04-03 16:45     阅读(308)     评论(0)     点赞(21)     收藏(1)


0

1

2

3

4

5

6

7

8

9

# =============================JZ16.合并两个排序的链表================================================
# 题目要求:给两个非递减单链表l1, l2,合并为一个非递减的单链表。
# =============================================================================


#链表学习1
 
class Node(object): #定义一个节点
    def __init__(self,elem):
        self.elem = elem
        self.next = None
class SingleLinkList(object):
    def __init__(self,node = None):
        self.__head = node  #特别需要注意的是,这个class中的self.__head指的是一个节点,也就是说凡是定义为self.__head的都是一个节点
    def is_empty(self):
        return self.__head == None
    def travel(self): #遍历函数
        #设置一个游标cur
        cur = self.__head  #cur现在指的位置是首地址指的位置
        while cur != None:
            print(cur.elem, end = " ")  #空格是禁止换行  利用空格代替\n
            cur = cur.next #游标向后移动
    def length(self):
        cur = self.__head  #cur现在指的位置是首地址指的位置
        #count 记录数量
        count = 0
        while cur != None:
            count += 1 
            cur = cur.next
        return count
    def addend(self,item):
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
    def addhead(self,item):
        node = Node(item)
        node.next = self.__head
        self.__head = node
    def insert(self,pos,item):
        if pos < 0:
            return self.addhead(item)
        elif pos > (self.length() - 1):
            return self.addend(item)
        else:
            pre = self.__head   #设置一个表示之前位置的游标pre
            count = 0
            while count < (pos -1):
                count += 1
                pre = pre.next 
            #当循环退出后,pre指向pos-1的位置
            node = Node(item)
            node.next = pre.next
            pre.next = node
    def search(self,item):
        cur = self.__head  #一定要记住,遇到计数的时候要用到游标,游标指向第一个节点
        while cur != None :
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False
        
    def remove(self,item):
        cur = self.__head
        pre = None 
        while cur != None:
            if cur.elem == item:
                if cur == self.__head: #先判断要删除的节点是不是头结点
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
        
        
        




            
ll = SingleLinkList()

print(ll.is_empty())
print(ll.length())
ll.addend(1)
print(ll.is_empty())
print(ll.length())

ll.addend(2)
ll.addend(3)   
ll.addend(4)
ll.addend(5)
ll.addend(6) 
ll.addhead(10)
ll.insert(2,100)
print(ll.length()) 
ll.travel()  
ll.search(100)
print()  #分段
ll.remove(100)
ll.travel()

0

1

2

3

4

5

6



所属网站分类: 技术文章 > 博客

作者:高富帅

链接: https://www.pythonheidong.com/blog/article/915267/6b068e50df9ef16b6a4a/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

21 0
收藏该文
已收藏

评论内容:(最多支持255个字符)