[数据结构与算法]leetcode刷题#day4

Python 中链表例题leetcode

首先分析python的链表是如何工作的，由于python本身是不带链表的，一般是由笔者自己定义一个class，然后令其实例化。具体看如下例子：

class ListNode():
    def __init__(self, val):
        if isinstance(val,int):
            self.val = val
            self.next = None
            
        elif isinstance(val,list):
            self.val = val[0]
            self.next = None
            cur = self
            for i in val[1:]:
                cur.next = ListNode(i)
                cur = cur.next
    
    def gatherAttrs(self):
        return ", ".join("{}: {}".format(k, getattr(self, k)) for k in self.__dict__.keys())

    def __str__(self):
            return self.__class__.__name__+" {"+"{}".format(self.gatherAttrs())+"}"
     
l1 = [2,4,8]
l2 = [5,6,4]
l1 = ListNode(l1)
l2 = ListNode(l2)

如果给定两个list，则可以按照以上方式去定义一个链表，但是怎么去创建更改一个新的链表呢，这就需要考虑到python中对象实例化的一个规则。如下：

class human():
    def __init__(self,name,age):
        self.name = name
        self.age = age
    
a = human('jin',3)
b,c = a,a #需要注意 此时 a,b,c荣辱与共
b.age = 23
print(a.age,c.age)

#ans: 23 23

也就是说我们定义一个实例化对象时，后续的更改是直接影响最初的实例化对象的，那如果想得到一个新的实例化对象，可以重新定义一个或者使用python的copy方法:

class human():
    def __init__(self,name,age):
        self.name = name
        self.age = age
    
a = human('jin',3)
c = human('jin',3)
#c = copy.deepcopy(a)
b = a
b.age = 23
print(a.age,c.age)

#ans 23 3

那既然有了这个性质，我们的链表就能简单实现想要的功能了。
首先是如何指向下一个节点以及做相应的修改

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode(l1.val+l2.val)
        # 首先初始化一个链表的节点[这里其实就是实例化对象]
        temp = res
        # 分配一个暂时的变量方便做相应的修改
        while (l1 and l1.next != None) or (l2 and l2.next != None) or (temp.val > 9):
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next
			sum_ = (l1.val if l1 else 0) + (l2.val if l2 else 0)
			#如果l1 l2当前节点有值则加 没有值则加0 注意不能与上面直接合并 l1 l2已经发生改变
            # sum_ 表示当前节点的结果
            temp.next = ListNode(temp.val//10 + sum_)
            # 根据我们定义的ListNode 给下一个节点赋值（说白了就是在节点后面再给他串一个节点 俗称迭代套娃）
            temp.val = temp.val%10
            # 更改本节点的值

            temp = temp.next
            # 把指针指向下一个节点 这样重复上述操作的话 就可以达到节点一个个往下串的效果
            
        return res

嗯 先捋到这吧