入门知识点
数据结构
是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。常用的数据结构有：数组，栈，链表，队列，树（二叉树），图，堆，散列表等等，（python内置数据结构：元组、列表、集合、字典）。
Python除了内置的四种容器外，还有collections库中有以下各种容器也是数据结构：
namedtuple |
创建命名元组子类的工厂函数，生成可以使用名字来访问元素内容的tuple子类 |
deque |
类似列表(list)的容器，实现了在两端快速添加(append)和弹出(pop) |
ChainMap |
类似字典(dict)的容器类，将多个映射集合到一个视图里面 |
Counter |
字典的子类，提供了可哈希对象的计数功能 |
OrderedDict |
字典的子类，保存了他们被添加的顺序，有序字典 |
defaultdict |
字典的子类，提供了一个工厂函数，为字典查询提供一个默认值 |
UserDict |
封装了字典对象，简化了字典子类化 |
UserList |
封装了列表对象，简化了列表子类化 |
UserString |
封装了字符串对象，简化了字符串子类化 |
另外， enum库中 Enum() 可以创建的枚举类型，也算是一种数据结构。
线性表
是某一类元素的抽象集合，记录元素之间一种顺序关系，是最基本的数据结构之一。根据它们的存储方式分为：顺序表和链表。
顺序表
是将表中的元素有顺序地存放在一大块连续存储区间里，这些元素间的顺序是与它们的存储顺序关联的。
链表
是将表中元素存放在一系列的节点中，这些节点通过连接构造成为链表。节点的存储位置可以是连续的，可以是不连续的，也就意味着它们可以存在任何内存未被占用的位置。根据它们的指针指向又可分为：单向链表、双向链表和循环链表，循环链表又能分为：单向循环链表和双向循环链表。
节点 Node
又称“结点”，由数据域和指针域组成。
单链表
又称单向链表，是一种链式的数据结构，链表中的数据用节点来表示，每个节点由数据元素和指向下一个数据元素的指针组成，指针就是连接每个节点的地址。也就是说它由很多个节点组成，节点之间用指针相连的链式存储结构，指针从前驱节点指向后继节点。单链表正是通过每个节点的指针域将线性表的数据元素按其逻辑次序链接在一起。单链表的第一个节点的存储位置叫做“头指针”，最后一个节点的指针为空。
头节点
头节点的设立是为了操作的统一和方便，是放在第一个元素的节点之前，它的数据域一般没有意义，并且它本身也不是链表必须要带的。那设立头节点的目的是什么呢？其实就是为了在某些时候可以更方便的对链表进行操作，有了头节点，我们在对第一个元素前插入或者删除节点的时候，它的操作与其它节点的操作就统一了。
头指针
顾名思义，是指向链表第一个节点的指针，如果有头节点的话，那么就是指向头节点的指针。它是链表的必备元素且无论链表是否为空，头指针都不能为空，因为在访问链表的时候总得知道它在什么位置，这样才能通过指针域找到下一个节点的位置，也就是说知道了头指针，整个链表的元素都是可访问的，所以它必须要存在，这也就是我们常说的“标识”，这也就是为什么要用头指针来表示链表。
单链表的实现
节点类
在C/C++中，通常采用“结构体+指针”来实现链表：
1. struct ListNode { 2. int Val 3. *ListNode Next 4. }
而在Python中没有指针，只能采用“类+引用”来模拟实现链表：
1. class Node(): 2. 3. def __init__(self, value=None, Next=None): 4. self.val = value 5. self.next = Next
C/C++中空指针的定义 int *ptr = NULL; ，Python 只能用 None 来表示为“空”。
创建节点
1. 创建空节点
数据域和指针域同时为None的节点
>>> node = Node() >>> node.val == None True >>> node.next == None True >>>
2. 非空单个节点
>>> node = Node(1) >>> node.val == 1 True >>> node.next == None True >>>
这个节点类的初始化方法__init__，有些文章里写成下面这样：
def __init__(self, value=None): self.val = value self.next = None
区别在于：后一种写法只能用.next来追加(后插)节点，因为后者在初始化时没法传递.next的参数，只能是一个值None；而前面那种写法不但可以追加，还能用嵌套的办法来前插节点。
3. 节点间的连接
连接方法无非就两种：追加和前插
>>> node = Node() >>> node.next = Node(1) >>> node.next.next = Node(2) >>> node.next.next.next = Node(3) >>> >>> >>> node2 = Node() >>> node2 = Node(1, node2) >>> node2 = Node(2, node2) >>> node2 = Node(3, node2) >>>
为了检测节点相连的状况，节点类添加 __str__、__repr__ 两个方法 (转化和打印)方便展示，不知道具体情况的，请见上一篇文章有详细介绍《以单链表为例，一步步深入了解类》（本篇不是上篇的简单重复，而是在学习过程中有些新的体会和发现）。废话少说，直接上代码以及重新执行的效果：
class Node(): def __init__(self, value=None, Next=None): self.val = value self.next = Next def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' ''' 测试效果： >>> node = Node() >>> node.next = Node(1) >>> node.next.next = Node(2) >>> node.next.next.next = Node(3) >>> node Node(None->1->2->3->None) >>> >>> node2 = Node() >>> node2 = Node(1, node2) >>> node2 = Node(2, node2) >>> node2 = Node(3, node2) >>> node2 Node(3->2->1->None->None) '''
上面的结果分别展现了追加和前插的区别，同时也能看到所建链表有无头节点的区别。
追加法的结果 Node(None->1->2->3->None) 刚好和前文定义章节里图三描述的有头节点的单链表一样。前一个None是头节点的数据域，后一个None是尾节点的指针域。
但是这放到前插法里有个小问题，前插到一个空节点时，结果为Node(3->2->1->None->None) ，头节点的空值被认作是一个节点元素了。
4. 判断对象是否为节点
内容有点多，另建一篇短文《如何判断一个对象是否为单链表的节点》来说明。
5. 判断节点是否为空
有了上文的经验，先要判断一下是否空节点再判断两个属性是否全为None：
>>> class Node(): def __init__(self, value=None, Next=None): self.val = value self.next = Next def isNode(node): return isinstance(node,Node) and isinstance(node.next,(Node,type(None))) def isEmpty(node): return isinstance(node,Node) and node.val==None==node.next >>> node = Node() >>> node.isNode() True >>> node.isEmpty() True >>> node1 = Node(1) >>> node1.isNode() True >>> node1.isEmpty() False >>>
6. 去掉头节点
如3.中所说，前插法会把数据插到头节点之前去，经过多次尝试，发现只有在初始化方法中加一个判断，就能和谐掉这个小问题；追加法的头节点，只能手工去掉返回值取.next的值即可；或者直接从第一元素开始赋值给节点：
>>> class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next if type(self.next)==Node and self.next.val==None: self.next=None def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' >>> a=Node() >>> a=Node(3,a) >>> a=Node(2,a) >>> a=Node(1,a) >>> a Node(1->2->3->None) >>> >>> >>> b=Node(1) >>> b.next=Node(2) >>> b.next.next=Node(3） >>> b Node(1->2->3->None) >>>
7. 约定：None 不被允许赋值给中间节点的数据域
即使赋值了，也会被强制中断；还有另一个好处在于尾节点的.next值也是None，这样不容易混淆。看以下测试：
1. >>> a = Node(1,Node(2,Node(None,Node(3)))) 2. >>> a 3. Node(1->2->None) 4. >>>
期望的 Node(1->2->None->3->None) 没有出现，到了第三个节点被 6. 中所设的判断语句给强行中断了。
8. 连续赋值
先来看一小段可以连续赋值的代码，近期与推导式杠上了：
>>> size = 10 >>> n = [Node(i+1) for i in range(0,size)] >>> t = [exec(f'n[{i-1}].next=n[{i}]') for i in range(size-1,0,-1)] >>> n[0] Node(1->2->3->4->5->6->7->8->9->10->None) # 换成函数即： def createNodeList(size = 10): n = [] for i in range(size): n.append(Node(i+1)) for i in range(size-1,0,-1): n[i-1].next = n[i] return n[0]
换成列表作参数：
>>> def createNodeList(lst = [2,3,11,5,6]): ret = Node() for i in lst[::-1]: ret = Node(i,ret) return ret >>> createNodeList() Node(2->3->11->5->6->None) >>> lst = [*range(1,10)] >>> createNodeList(lst) Node(1->2->3->4->5->6->7->8->9->None) >>>
9. 连续赋值方法
扩展成多参数函数，写成类的方法，几乎可以支持所有数据类型：
class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next if type(self.next)==Node and self.next.val==None: self.next=None def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' def build(*data, split=True): '''把数据转换成节点链表''' lst,ret = [],Node() for val in data: if type(val) is str: if not split: lst.append(val) continue if str=='': continue try: num = int(val) lst.extend([int(_) for _ in val]) except: lst.extend([_ for _ in val]) elif hasattr(val,'__iter__'): lst.extend([_ for _ in val]) elif Node.isNode(val): if not val.isNone: lst.extend(val.values) else: lst.append(val) for i in lst[::-1]: ret = Node(i, ret) return ret ''' >>> Node.build(1,2,3,4,5,9) Node(1->2->3->4->5->9->None) >>> Node.build(range(1,5),5,6,[7,8,9]) Node(1->2->3->4->5->6->7->8->9->None) >>> Node.build({1,2,3},(5,6),Node(7,Node(8)),9) Node(1->2->3->5->6->7->8->9->None) >>> >>> Node.build('1234','abcd','12ab') Node(1->2->3->4->a->b->c->d->1->2->a->b->None) >>> Node.build('1234','abcd','12ab',split=False) Node(1234->abcd->12ab->None) >>> '''
其中，split参数用于设置是否要拆分字符串，默认为True 表示要拆分成单个字符。
这几乎是万能的节点创建方法，至于单个元素的添加，追加、多节点拼接等就此省略了，其相关内容也在前文《触“类”旁通：以单链表为例，一步步深入了解类》里说过。
节点链的遍历
内部方法 __str__和__repr__ 已经展现了遍历，但都是文本形式，我们需要的数据，遍历所有节点的数据域存放到列表中返回，代码和注释如下：
>>> node = Node.build(2,3,4,7,8,9) >>> node # 创建一个待遍历的节点链表 Node(2->3->4->->8->9->None) >>> ret = [] # 存入数据的列表 >>> ptr = node # 相当于设置一个指向链表的“指针” >>> while ptr is not None: # 从头节点开始循环，到尾节点的指针域为空值止 ret.append(ptr.val) # 取出当前节点的数据域，追加到列表中 ptr = ptr.next # 相当于“指针”向后一个节点移动 >>> print(ret) [2, 3, 4, 7, 8, 9] >>>
注意： while ptr is not None: 中的is not None 可以省略，while ptr: ... 仿佛代码显得更 pythonic ；但不建议省，更不能写成： while ptr.val: ... 这样碰到0元素也会终止；而到尾节点会报错，因为None没有.val属性。
这个遍历过程还可以改写成元素列表values属性 和 列印方法 pprint() 等，完整的代码如下：
class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next if type(self.next)==Node and self.next.val==None: self.next=None def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' @property def values(self): ret,ptr = [],self while ptr is not None: ret.append(ptr.val) ptr = ptr.next return ret def pprint(self): print('->'.join([str(i) for i in self.values])) def isNode(node): return isinstance(node,Node) and isinstance(node.next,(Node,type(None))) def build(*data, split=True): '''把数据转换成节点链表''' lst,ret = [],Node() for val in data: if type(val) is str: if not split: lst.append(val) continue if str=='': continue try: num = int(val) lst.extend([int(_) for _ in val]) except: lst.extend([_ for _ in val]) elif hasattr(val,'__iter__'): lst.extend([_ for _ in val]) elif type(val) is Node: if not val.isNone: lst.extend(val.values) else: lst.append(val) ret = Node() for i in lst[::-1]: ret = Node(i, ret) return ret
# 效果测试： >>> node = Node.build(2,3,4,7,8,9) >>> node.values [2, 3, 4, 7, 8, 9] >>> node.pprint() 2->3->4->7->8->9 >>>
┃ 万能偷懒大法 ┃
┗───────────┛
有了.values 这个只读属性后，所有单链表相关的问题都能用“万能偷懒大法”来完成，就是说不管你有几个链表，都全部遍历成数据列表，这样就把链表问题转化成非链表的普通问题，最后结果用 Node.build() 重建成链表输出。哈哈，是不是万能的，只是不推荐！学习链表知识，还是要学会用正规的方法在遍历的同时解决问题，这才是正道！
遍历的应用
1. 求链表的长度
不要取出数据只要计数即可，此方法可用于重载len()函数或者设为只读属性self.length
def __len__(self): if self.val is None: return 0 length,ptr = 0,self while ptr is not None: length += 1 ptr = ptr.next return length def size(): return self.__len__() @property def length(self): return self.size()
2. 比较两个链表是否相等
要求两表的所有节点值全部对应相等，可用于重载比较运算符 == 。以下列出所有代码，因为其过程中调用了len()，其实这算是偷懒的办法，两链表各遍历了两次；好的算法遍历一次即可，读者可以自己试一下：
class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next if type(self.next)==Node and self.next.val==None: self.next=None def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' def __len__(self): if self.val is None: return 0 length,ptr = 0,self while ptr is not None: length += 1 ptr = ptr.next return length def __eq__(self, other): ptr1,ptr2 = self,other if len(ptr1)!=len(ptr2): return False while ptr1 is not None: if ptr1.val!=ptr2.val: return False ptr1 = ptr1.next ptr2 = ptr2.next else: return True def size(): return self.__len__() @property def length(self): return self.size()
3. 复制链表
直接用=赋值，相当于设置了一个指针，一个有数值变化另一个也作相应变化；只有靠遍历逐个复制出节点值才算直的拷贝，这就是直接赋值和浅拷贝的区别。（如果将对象中嵌套的子对象也逐个复制出来那就是“深拷贝”）
def copy(node): ret = Node() ptr1,ptr2 = node,ret while ptr1 is not None: ptr2.next = Node(ptr1.val) ptr1,ptr2 = ptr1.next,ptr2.next return ret.next ''' >>> node1 = Node.build(1,2,3,4,5) >>> node2 = Node.copy(node1) >>> node2 Node(1->2->3->4->5->None) >>> node2.next.next.val = 0 >>> node2 Node(1->2->0->4->5->None) >>> node1 Node(1->2->3->4->5->None) >>> >>> # 对比一下： >>> node1 = Node.build(1,2,3,4,5) >>> node2 = node1 >>> node2.next.next.val = 0 >>> node2 Node(1->2->0->4->5->None) >>> node1 Node(1->2->0->4->5->None) >>> '''
4. 链表的拼接
链表的连接方法： node1.cat(node2) 和 join(node1,node2)，两者的区别在于前者cat的node2直接追加到node1后，node1变更为拼接结果，node2不变；后者join只返回拼接结果，node1、node2的值都不变。
def cat(self,node): ptr = self while ptr.next is not None: ptr = ptr.next ptr.next = node return self def join(node1,node2): ret = Node() p,p1,p2 = ret,node1,node2 while p1 is not None: p.next = Node(p1.val) p,p1 = p.next,p1.next while p2 is not None: p.next = Node(p2.val) p,p2 = p.next,p2.next return ret.next ''' >>> a = Node.build(1,2,3) >>> b = Node.build(4,5) >>> Node.join(a,b) Node(1->2->3->4->5->None) >>> a Node(1->2->3->None) >>> b Node(4->5->None) >>> >>> a.cat(b) Node(1->2->3->4->5->None) >>> a Node(1->2->3->4->5->None) >>> b Node(4->5->None) >>> '''
5. 有条件的部分复制
比如说，要将一个链表中的奇数值，依次复制到另一个链表中：
def copyif(node): ret = Node() ptr1,ptr2 = node,ret while ptr1 is not None: if ptr1.val%2: ptr2.next = Node(ptr1.val) ptr2 = ptr2.next ptr1 = ptr1.next return ret.next ''' >>> node1 = Node.build(range(10)) >>> node1 Node(0->1->2->3->4->5->6->7->8->9->None) >>> node2 = Node.copyif(node1) >>> node2 Node(1->3->5->7->9->None) >>> '''
上面这个框架很重要，几乎可用作模版来解决很多问题了。以下看实战：
实战链表遍历
遍历实战一：
给定一个已排序链表，删除重复节点，原始链表中多次出现的数字只能保留一次。
示例1
输入: 1->1->2
输出: 1->2
示例2
输入: 1->1->2->3->3
输出: 1->2->3
class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next if type(self.next)==Node and self.next.val==None: self.next=None def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' def build(*data, split=True): '''把数据转换成节点链表''' lst,ret = [],Node() for val in data: if type(val) is str: if not split: lst.append(val) continue if str=='': continue try: num = int(val) lst.extend([int(_) for _ in val]) except: lst.extend([_ for _ in val]) elif hasattr(val,'__iter__'): lst.extend([_ for _ in val]) elif type(val) is Node: if not val.isNone: lst.extend(val.values) else: lst.append(val) ret = Node() for i in lst[::-1]: ret = Node(i, ret) return ret def removeDup(node): '''删除重复节点，重复的只保留一次''' ret = Node() p1,p2 = node,ret # 相当于设置了2个“指针” while p1 is not None: if p1.val != p2.val: p2.next = Node(p1.val) p2 = p2.next p1 = p1.next # “指针”向后移动 return ret.next # 加上.next 去掉“空”的“头节点” ''' >>> a = Node.build(1,1,2) >>> a Node(1->1->2->None) >>> Node.removeDup(a) Node(1->2->None) >>> b = Node.build(1,1,2,3,3) >>> b Node(1->1->2->3->3->None) >>> Node.removeDup(b) Node(1->2->3->None) >>> c = Node.build(1,2,2,3,4,4,4,5) >>> c Node(1->2->2->3->4->4->4->5->None) >>> Node.removeDup(c) Node(1->2->3->4->5->None) >>> '''
遍历实战二：
给定一个排序链表，删除所有重复的节点，留原始链表有过重复的数字一个也不留。
示例1
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例2
输入: 1->1->1->2->3
输出: 2->3
class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next if type(self.next)==Node and self.next.val==None: self.next=None def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' def build(*data, split=True): '''把数据转换成节点链表''' lst,ret = [],Node() for val in data: if type(val) is str: if not split: lst.append(val) continue if str=='': continue try: num = int(val) lst.extend([int(_) for _ in val]) except: lst.extend([_ for _ in val]) elif hasattr(val,'__iter__'): lst.extend([_ for _ in val]) elif type(val) is Node: if not val.isNone: lst.extend(val.values) else: lst.append(val) ret = Node() for i in lst[::-1]: ret = Node(i, ret) return ret def isNode(node): return isinstance(node,Node) and isinstance(node.next,(Node,type(None))) def removeDup2(node): '''删除重复节点，重复过的全部不保留''' ret = Node() p1,p2 = node,ret if not Node.isNode(p1.next): return node if p1.val != p1.next.val: p2.next = Node(p1.val) p2 = p2.next t = p1.val p1 = p1.next while p1.next is not None: if t != p1.val != p1.next.val: p2.next = Node(p1.val) p2 = p2.next t = p1.val p1 = p1.next if t != p1.val: p2.next = Node(p1.val) return ret.next if ret.next!=None else Node() ''' >>> a = Node.build(1,2,3,3,4,4,5) >>> a Node(1->2->3->3->4->4->5->None) >>> Node.removeDup2(a) Node(1->2->5->None) >>> b = Node.build(1,1,1,2,3) >>> b Node(1->1->1->2->3->None) >>> Node.removeDup2(b) Node(2->3->None) >>> c = Node.build(1,2,2,3,4,4,4,5) >>> c Node(1->2->2->3->4->4->4->5->None) >>> Node.removeDup2(c) Node(1->3->5->None) >>> '''
此题，只遍历链表中的头尾节点除外的中间节点，各自与前后两个节点的值对比，都不相等的写入新链表；头、尾节点只要对比各自的后续节点和前驱节点，不相等的写入新链表。
遍历实战三：
给定两个有序链表(升序)，合并为一个新的有序链表并返回。
示例1
输入：1->2>4->8
1->3->3->5->5
输出：1->1->2->3->3->4->5->5->8
示例2
输入：0->2>4->8
1->3->5->7->9
输出：0->1->2->3->4->5->6->7->8->9
class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next if type(self.next)==Node and self.next.val==None: self.next=None def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' @property def values(self): ret,ptr = [],self while ptr is not None: ret.append(ptr.val) ptr = ptr.next return ret def pprint(self): print('->'.join([str(i) for i in self.values])) def isNode(node): return isinstance(node,Node) and isinstance(node.next,(Node,type(None))) def build(*data, split=True): '''把数据转换成节点链表''' lst,ret = [],Node() for val in data: if type(val) is str: if not split: lst.append(val) continue if str=='': continue try: num = int(val) lst.extend([int(_) for _ in val]) except: lst.extend([_ for _ in val]) elif hasattr(val,'__iter__'): lst.extend([_ for _ in val]) elif type(val) is Node: if not val.isNone: lst.extend(val.values) else: lst.append(val) ret = Node() for i in lst[::-1]: ret = Node(i, ret) return ret def merge(node1, node2): '''合并两个有序链表''' ret = Node() ptr,ptr1,ptr2 = ret,node1,node2 while ptr1 is not None and ptr2 is not None: if ptr1.val < ptr2.val: ptr.next = Node(ptr1.val) ptr1 = ptr1.next else: ptr.next = Node(ptr2.val) ptr2 = ptr2.next ptr = ptr.next ptr.next = ptr1 or ptr2 # 因为有大小比较，两者只可能一个为非空 return ret.next ''' >>> n1 = Node.build(1,2,4,8) >>> n2 = Node.build(1,3,3,5,5) >>> n1,n2 (Node(1->2->4->8->None), Node(1->3->3->5->5->None)) >>> Node.merge(n1,n2).pprint() 1->1->2->3->3->4->5->5->8 >>> n1 = Node.build(0,2,4,8) >>> n2 = Node.build(1,3,5,7,9) >>> n1,n2 (Node(0->2->4->8->None), Node(1->3->5->7->9->None)) >>> Node.merge(n1,n2).pprint() 0->1->2->3->4->5->7->8->9 >>> '''
其中： ptr.next = ptr1 or ptr2 的小技巧，来自逻辑或运算(or)的特性：
>>> a = Node.build(2,4,3) >>> b = Node.build(5,6,4) >>> a or b Node(2->4->3->None) >>> a = Node() >>> a or b Node(5->6->4->None) >>>
再看一个用了此特性的递归法，是如何解决本题的：
def merge1(node1, node2): '''递归法合并两个有序链表''' if node1 is None or node2 is None: return node1 or node2 nod1 = Node(node1.val,node1.next) # 创建临时变量，使传入的参数保留原值 nod2 = Node(node2.val,node2.next) # 在函数体外复制，建议用 nodex=nodex.copy() if nod1.val < nod2.val: nod1.next = Node.merge1(nod1.next,nod2) return nod1 else: nod2.next = Node.merge1(nod1,nod2.next) return nod2
注：此递归函数的参数只能是非空节点。
遍历实战四：
给定两个逆序表达整数各位数字的链表，求出两数之和的逆序表达的链表。
示例1
输入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7->0->8
解释: 342 + 465 = 807
示例2
输入: (1->) + (9 -> 9 -> 9)
输出: 0->0->0->1
解释: 1 + 999 = 1000
def addition(node1,node2): if not(Node.isNode(node1) and Node.isNode(node2)): raise TypeError('Both node1 and node2 must be Node') if node1.val is None: # 如是空节点，默认这个加数为零 node1 = Node(0) if node2.val is None: node2 = Node(0) ret = Node() p,p1,p2 = ret,node1,node2 # 设置“指针” Sum = carry = 0 # 各位上的和、进位 flag = 0 # 节点遍历结束的标记 while Node.isNode(p1) or Node.isNode(p2): if flag==0: Sum = p1.val+p2.val+carry p1,p2 = p1.next,p2.next if not Node.isNode(p1):flag=1 if not Node.isNode(p2):flag=2 elif flag==1: Sum = p2.val+carry p2 = p2.next elif flag==2: Sum = p1.val+carry p1 = p1.next carry = 1 if Sum>9 else 0 p.next = Node(Sum%10) p = p.next if carry==1: p.next=Node(1) return ret.next ''' # 测试结果： >>> a = Node.build(2,4,3) >>> b = Node.build(5,6,4) >>> addition(a,b) Node(7->0->8->None) >>> >>> a = Node.build(1) >>> b = Node.build(9,9,9) >>> addition(a,b) Node(0->0->0->1->None) >>> '''
本题主要搞定一个进位问题，最高位如还有进位，则尾节点后再加一个Node(1)。上面解法设置了遍历标记flag，另外也可以不设标记，照实战三中的思路，到其中一个短的链表(哪个更短未知)遍历结束后，再设一个新指针 ptr3 指向 (ptr1 or ptr2)，即指向两者中较长者的多余节点部分(一样长为空)，再与carry进位逐位相加。代码如下：
def addition2(node1, node2): if not(Node.isNode(node1) and Node.isNode(node2)): raise TypeError('Both node1 and node2 must be Node') if node1.val is None: # 如是空节点，默认这个加数为零 node1 = Node(0) if node2.val is None: node2 = Node(0) ret = Node() Sum = carry = 0 ptr,ptr1,ptr2 = ret,node1,node2 while ptr1 is not None and ptr2 is not None: Sum = ptr1.val + ptr2.val + carry carry = 1 if Sum > 9 else 0 ptr.next = Node(Sum % 10) ptr,ptr1,ptr2 = ptr.next,ptr1.next,ptr2.next ptr3 = ptr1 or ptr2 # 设置新指针，指向长指针的余下部分 while ptr3 is not None: Sum = ptr3.val + carry carry = 1 if Sum > 9 else 0 ptr.next = Node(Sum % 10) ptr,ptr3 = ptr.next,ptr3.next if carry: ptr.next = Node(1) return ret.next
遍历实战五：
合并k个已排序的链表，并将其作为一个已排序的列表返回。实战三的升级版
示例
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
由于k是可变的，初看题目好像很高深；想不出什么特殊法子，如有k个链表需要合并，不可能同时设k个指针同时遍历它们；于是只能分而治之，就是不停调用实战三中的merge()就可解决。实际上调用函数 Merge() 很简单，只要一句循环即可，执行k遍被调用函数 merge() ；关键是临时变量 ret 的初值一定要设为 None 而不是 Node()，否则第一步就会报错。代码如下：
def Merge(*nodes): ret = None for node in nodes: ret = Node.merge(ret,node) return ret ''' >>> nodes = [] >>> nodes.append(Node.build(1,4,5)) >>> nodes.append(Node.build(1,3,4)) >>> nodes.append(Node.build(2,6)) >>> nodes [Node(1->4->5->None), Node(1->3->4->None), Node(2->6->None)] >>> Node.Merge(*nodes) Node(1->1->2->3->4->4->5->6->None) >>> >>> nodes.append(Node.build(7,8,9)) >>> nodes.append(Node.build(0,2,8)) >>> Node.Merge(*nodes) Node(0->1->1->2->2->3->4->4->5->6->7->8->8->9->None) >>> '''
注：以上几个实战真题，都是来自 leetcode 中关于链表的问题。可能都会有更好的思路和解法，没刷过这些题目的就自己动手试试吧，实战出真知！
本篇完......更多内容 To be continue...
附：数据结构相关术语
相关术语：
数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。
数据元素：数据（集合）中的一个“个体”，数据及结构中讨论的基本单位。
数据项：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
数据类型：在一种程序设计语言中，变量所具有的数据种类。整型、浮点型、字符型等等。
逻辑结构：数据之间的相互关系。
１. 集合：结构中的数据元素除了同属于一种类型外，别无其它关系
２. 线性结构：数据元素之间一对一的关系
３. 树形结构：数据元素之间一对多的关系
４. 图状结构或网状结构：结构中的数据元素之间存在多对多的关系
物理结构/存储结构：数据在计算机中的表示。物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、哈希结构）等。
在数据结构中,从逻辑上可以将其分为线性结构和非线性结构。
数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。实现应用程序是“逻辑结构”，存储的是“物理结构”。逻辑结构主要是对该结构操作的设定，物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、希哈结构）等。
顺序存储结构中，线性表的逻辑顺序和物理顺序总是一致的。但在链式存储结构中，线性表的逻辑顺序和物理顺序一般是不同的。
算法五个特性： 有穷性、确定性、可行性、输入、输出。
算法设计要求：正确性、可读性、健壮性、高效率与低存储量需求。(好的算法)
算法的描述有伪程序、流程图、N-S结构图等。E-R图是实体联系模型，不是程序的描述方式。
设计算法在执行时间时需要考虑：算法选用的规模、问题的规模。
时间复杂度：算法的执行时间与原操作执行次数之和成正比。时间复杂度：O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n) O(n! ) O(n^n)
空间复杂度：若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。
