单向链表
节点类、链表类基本方法
开始刷题前先罗列一下单向链表的近40个基本属性和方法,大多数出自《触“类”旁通5|链表类才是单链表的主咖》一篇并且已是验证过的。仅用于方便创建和展示单链表,碰到实际问题时尽可能只用到类的初始化方法,而不是直接调用初始化之外的其他方法来解决问题。
class Node(): def __init__(self, value=None, Next=None): self.val = value self.next = Next if (type(self.next)==Node and self.next.val==None or type(self.next)!=Node and self.next!=None): self.next = None def __repr__(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 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 val is not None: lst.extend(val.values) elif type(val) is List: if val.head is not None: lst.extend(val.head.values) else: lst.append(val) ret = Node() for i in lst[::-1]: ret = Node(i, ret) return ret class List(): def __init__(self, *node): self.head = Node.build(*node) def __repr__(self): return f'[{self.head}]' def __len__(self): return self.size() @property def length(self): return self.size() def is_empty(self): if self.head.val==None: return True else: return False def size(self): ret,ptr = 0,self.head if ptr.val==None: return 0 while ptr: ptr = ptr.next ret += 1 return ret def copy(self): return List(self.head) @property def tail(self): ptr = self.head while ptr.next: ptr = ptr.next return ptr @property def values(self): if self.is_empty(): return [] ret,ptr = [],self.head while ptr: ret.append(ptr.val) ptr = ptr.next return ret @property def items(self): ptr = self.head while ptr: yield ptr.val ptr = ptr.next def NthNode(self, n=1): ptr = self.head for _ in range(n-1): if ptr.next is None: raise ValueError('n large then length of List') ptr = ptr.next return ptr def NthNodefromEnd(self, n=1): fast = slow = self.head for _ in range(n): if fast is None: raise ValueError('n large then length of List') fast = fast.next while fast: fast,slow = fast.next,slow.next return slow def __contains__(self, data): if self.is_empty(): return False if isinstance(data,List): data = data.head if isinstance(data,Node): count = self.find(data.val)+1 if count==0: return False ptr1,ptr2 = self.head,data for _ in range(1,count): ptr1 = ptr1.next if ptr1 is None: return False while ptr2: if ptr1 is None or ptr1.val!=ptr2.val: return False ptr1,ptr2 = ptr1.next,ptr2.next return True else: return bool(1 + self.find(data)) def __eq__(self, data): if not isinstance(data,List): return False if data.is_empty(): if self.is_empty(): return True else: return False #return data in self and self in data ptr1,ptr2 = self.head,data.head while ptr1: if ptr1.val!=ptr2.val: return False ptr1,ptr2 = ptr1.next,ptr2.next return True def push(self, data): if not isinstance(data, List): data = List(data) if self.is_empty(): self.head = data.head else: ret = data.head ret.next,self.head = self.head,ret return self def append(self, data): if not isinstance(data, List): data = List(data) if self.is_empty(): self.head = data.head else: ptr = self.head while ptr.next: ptr = ptr.next ptr.next = data.head return self def cat(self, *data): for val in data: self.append(val) return self def __add__(self, *data): self.cat(*data) return self def __radd__(self, *data): self.add(*data) return self def __getitem__(self, item): return self.values[item] def __setitem__(self, idx, value): length = self.size() if idx<0: idx += length if self.is_empty() or idx+1>length or idx<0: raise IndexError('List() index out of range.') if isinstance(value,Node) or isinstance(value,List): raise TypeError('value type Error') ptr = self.head for i in range(idx): ptr = ptr.next ptr.val = value def __delitem__(self, index): length = self.size() if index<0: index += length if self.is_empty() or index+1>length or index<0: raise IndexError('List() index out of range.') ptr = self.head if index>0: for i in range(index-1): ptr = ptr.next ptr.next = ptr.next.next else: if ptr.next is None: self.head = Node() else: self.head = self.head.next return self delete = __delitem__ def nlargest(self): if self.is_empty(): return None ptr,ret = self.head,self.head.val while ptr: ret = max(ret, ptr.val) ptr = ptr.next return ret def nsmallest(self): if self.is_empty(): return None ptr,ret = self.head,self.head.val while ptr: ret = min(ret, ptr.val) ptr = ptr.next return ret def find(self, num): if self.is_empty(): return -1 ptr,ret = self.head,-1 while ptr: ret += 1 if ptr.val == num: break ptr = ptr.next else: ret = -1 return ret def index(self, num): error = lambda i:ValueError(f'{i} is not in List') if self.is_empty(): raise error(num) ptr,ret = self.head,-1 while ptr: ret += 1 if ptr.val == num: break ptr = ptr.next else: raise error(num) return ret def sort(self): length = self.size() for i in range(1, length): ptr = self.head for j in range(length - i): if ptr.val>ptr.next.val: ptr.val,ptr.next.val = ptr.next.val,ptr.val ptr = ptr.next return self def sorted(self): if self.size()<2: return self return List(self.head).sort() def reverse(self): ptr,ret = self.head,Node() while ptr: ret,ptr = Node(ptr.val,ret),ptr.next self.head = ret return self def __reversed__(self): ret = List(self) return ret.reverse() def rotate(self, k): '''链表旋转|k|个节点,正数向左负数向右''' if k==0: return self dbouble,size = Node(self.head.val),0 ptr,ptr1 = self.head,dbouble while ptr.next: ptr1.next = Node(ptr.next.val) ptr,ptr1 = ptr.next,ptr1.next ptr = self.head while ptr: size += 1 ptr1.next = Node(ptr.val) ptr,ptr1 = ptr.next,ptr1.next k %= size if k==0: return self ret = Node() ptr,ptr1 = dbouble,ret for i in range(k+size): if i>=k: ptr1.next = Node(ptr.val) ptr1 = ptr1.next ptr = ptr.next return List(ret.next) def __lshift__(self, n): self.head = self.rotate(n).head return self def __rshift__(self, n): self.head = self.rotate(-n).head return self
后补的几个方法:
def insert(self,index,value): if index==0: self.push(value) return self length = self.size() if index==length: self.append(value) return self elif index>length or index<0: raise ValueError('range: 0 <= index <= length of List') ptr,ret = self.head,Node(value) for _ in range(1,index): ptr = ptr.next ret.next,ptr.next = ptr.next,ret return self def pophead(self): if not self: raise IndexError('pophead from empty Node') ret,self.head = self.head.val,self.head.next or Node() return ret def poptail(self): if not self: raise IndexError('poptail from empty Node') ret = Node() ptr,ptr1 = self.head,ret while ptr.next: ptr1.next = Node(ptr.val) ptr,ptr1 = ptr.next,ptr1.next tail,self.head = ptr.val,ret.next or Node() return tail
leetcode单链表专场
其中前11题在《触“类”旁通2》和《触“类”旁通3》中用节点类练习过,本篇将用链表类重新写过。
1. 整数的链表加法
Add Two Numbers (#2)
给定两个逆序表达整数各位数字的链表,求出两数之和的逆序表达的链表。
示例
输入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7->0->8
解释: 342 + 465 = 807
输入: (1->) + (9 -> 9 -> 9)
输出: 0->0->0->1
解释: 1 + 999 = 1000
def addition(self, nodeList): if not (self and nodeList): return self or nodeList ret,carry = List(),0 ptr,ptr1,ptr2 = ret.head,self.head,nodeList.head while ptr1 and ptr2: 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 ptr1 = ptr1 or ptr2 while ptr1: Sum = ptr1.val+carry carry = 1 if Sum>9 else 0 ptr.next = Node(Sum%10) ptr,ptr1 = ptr.next,ptr1.next if carry: ptr.next = Node(1) return List(ret.head.next)
>>> a = List(2,4,3) >>> b = List(5,6,4) >>> a.addition(b) [7->0->8->None] >>> b.addition(a) [7->0->8->None] >>> List.addition(a,b) [7->0->8->None] >>> a [2->4->3->None] >>> b [5->6->4->None] >>> >>> a = List(1) >>> b = List(9,9,9) >>> List.addition(a,b) [0->0->0->1->None] >>> List.addition(b,a) [0->0->0->1->None] >>> a,b ([1->None], [9->9->9->None]) >>>
方法二:递归法
def Add2Nums(self, node, carry=0): if isinstance(self,List): self = List(self).head if isinstance(node,List): node = List(node).head if not (self or node): return Node(1) if carry else None self,node = self or Node(0), node or Node(0) Sum = self.val + node.val + carry self.val,self.next = Sum%10,List.Add2Nums(self.next,node.next,int(Sum>9)) return self
>>> list1 = List(2,4,3); list2 = List(5,6,4) >>> list1.Add2Nums(list2) 7->0->8->None >>> list2.Add2Nums(list1) 7->0->8->None >>> list1 = List(9,9,9); list2 = List(1) >>> list1.Add2Nums(list2) 0->0->0->1->None >>> list2.Add2Nums(list1) 0->0->0->1->None >>>
2. 删除倒数第N个节点
Remove Nth Node From End of List (#19)
给定链表,删除其倒数第n个节点,返回它的头指针。
示例
输入: 1->2->3->4->5, and n = 2.
输出: 1->2->3->5.
def removeNthEnd(self, n): head,size = self.head,0 while head: size += 1 head = head.next head = self.head if n>size or n<1: raise ValueError('n range out of [1,self.size]') if size==n: self.head = head.next if n!=1 else Node() else: for i in range(1,size-n): head = head.next head.next = head.next.next return self
>>> list1 = List(range(1,6)) >>> list1.removeNthEnd(2) [1->2->3->5->None] >>> list1.removeNthEnd(1) [1->2->3->None] >>> list1.removeNthEnd(3) [2->3->None] >>> list1.removeNthEnd(2) [3->None] >>> list1.removeNthEnd(1) [None->None] >>>
方法二:定位倒数第n个位置时,先用快指针从头向后移动n个位置,再用慢指针从头开始和快指针从n位置同时向后反复步进1个位置;当快指针达到尾部时慢指针刚好到达倒数第n的位置。
def delNthNodefromEnd(self, n=1): fast,ret = self.head,Node() for _ in range(n): if fast is None: raise ValueError('n large then length of List') fast = fast.next slow,ptr = self.head,ret while fast: ptr.next = Node(slow.val) fast,slow,ptr = fast.next,slow.next,ptr.next ptr.next = slow.next return List(ret.next)
>>> list1 = List(1,2,3,4,5) >>> for i in range(1,6): list1.delNthNodefromEnd(i) [1->2->3->4->None] [1->2->3->5->None] [1->2->4->5->None] [1->3->4->5->None] [2->3->4->5->None]
直接调用已定义的基本方法.delete()也能完成任务:
>>> list1 = List(range(1,6)) >>> n = 2 >>> del list1[-n] >>> list1 [1->2->3->5->None] >>> list1 = List(range(1,6)) >>> n = 2 >>> list1.delete(-n) [1->2->3->5->None] >>>
3. 合并有序链表
Merge Two Sorted Lists (#21)
给定两个有序链表(升序),合并为一个新的有序链表并返回。
示例
输入:1->2>4->8
1->3->3->5->5
输出:1->1->2->3->3->4->5->5->8
输入:0->2>4->8
1->3->5->7->9
输出:0->1->2->3->4->5->6->7->8->9
def merge(self, nodeList): '''合并两个有序链表''' if not self: return nodeList ret = List() ptr,ptr1,ptr2 = ret.head,self.head,nodeList.head while ptr1 and ptr2: 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 List(ret.head.next)
>>> list1 = List(1,2,4,8) >>> list2 = List(1,3,3,5,5) >>> list1.merge(list2) [1->1->2->3->3->4->5->5->8->None] >>> list1 [1->2->4->8->None] >>> list2 [1->3->3->5->5->None] >>> list1 = List(2,4,6,8) >>> list2 = List(1,3,5,7,9) >>> list2.merge(list1) [1->2->3->4->5->6->7->8->9->None] >>> list1,list2 ([2->4->6->8->None], [1->3->5->7->9->None]) >>> List.merge(list1,list2) [1->2->3->4->5->6->7->8->9->None] >>>
方法二:递归法
def mergeNodes(self,node): if isinstance(self,List): self = List(self).head if isinstance(node,List): node = List(node).head if not (self and node): return self or node if self.val <= node.val: self.next = List.mergeNodes(self.next,node) return self else: node.next = List.mergeNodes(self,node.next) return node
>>> list1 = List(1,2,4,8); list2 = List(1,3,3,5,5) >>> list1.mergeNodes(list2) 1->1->2->3->3->4->5->5->8->None >>> list2.mergeNodes(list1) 1->1->2->3->3->4->5->5->8->None >>> list1,list2 ([1->2->4->8->None], [1->3->3->5->5->None]) >>> list1.mergeNodes(list1) 1->1->2->2->4->4->8->8->None >>> list2.mergeNodes(list2) 1->1->3->3->3->3->5->5->5->5->None >>>
4. 合并多个有序链表
Merge k Sorted Lists (#23)
合并k个已排序的链表,并将其作为一个已排序的列表返回。前一题的升级版
示例
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
def Merge(self, *nodeList): ret = List(self.head) for lst in nodeList: ret = ret.merge(lst) return ret
5. 成对反转节点
Swap Nodes in Pairs (#24)
给定一个链表,每两个相邻节点交换一次,并返回其头指针。要求不能修改节点的数据域,假设或有成单的尾节点不反转。
示例
输入: 1->2->3->4.
输出: 2->1->4->3.
def swapPairs(self): if not self.head.next: return self ptr1 = ptr2 = self.head ret = List() ptr,ptr1 = ret.head,ptr1.next while ptr1: ptr.next = Node(ptr1.val) ptr = ptr.next ptr.next = Node(ptr2.val) ptr = ptr.next ptr1,ptr2 = ptr1.next,ptr2.next if not ptr1: break if not ptr1.next: ptr.next = Node(ptr1.val) ptr1,ptr2 = ptr1.next,ptr2.next self.head = ret.head.next return self
>>> a = List(1,2,3,4) >>> a.swapPairs() [2->1->4->3->None] >>> b = List(1,2,3,4,5) >>> b.swapPairs() [2->1->4->3->5->None]
方法二:迭代法
def swap2pair(self): if isinstance(self,List): self = List(self.head) self = self.head if not self or not self.next: return self ptr = self.next self.next = List.swap2pair(ptr.next) ptr.next = self return ptr
>>> a = List(1,2,3,4) >>> a.swap2pair() 2->1->4->3->None >>> b = List(1,2,3,4,5) >>> b.swap2pair() 2->1->4->3->5->None # 迭代法返回的是节点Node()的链式结构而非链表List()
6. 成组反转节点
Reverse Nodes in k-Group (#25)
给定一个链表,每k个相邻节点为一组,各组一一反转,返回修改后的列表。k小于或等于链表的长度。如果节点的数量不是k的倍数,那么最后剩下的个数小于k不满一组的则保持原样不反转。
示例
输入: 1->2->3->4->5.
输出: k=2时,2->1->4->3->5;
k=3时,3->2->1->4->5.
def reverseKGroup(self, k): if type(k) is not int or k<1: raise BaseException('K = 1, 2, 3, ...') if k==1: return self ret,self = Node(),List(self) ptr,ptr1 = self.head,ret size = 0 while True: kgroup = Node() ptr2 = kgroup count = 0 for _ in range(k): size += 1 if ptr is None: if k>=size: raise BaseException('length of Node less than K') break ptr2.next = Node(ptr.val) count += 1 ptr,ptr2 = ptr.next,ptr2.next kgroup = kgroup.next if count==k: t,p = None,kgroup while p: p.next,t,p = t,p,p.next kgroup = t ptr2 = kgroup for _ in range(k): ptr1.next = Node(ptr2.val) ptr1,ptr2 = ptr1.next,ptr2.next else: ptr1.next = kgroup break self.head = ret.next return self
>>> a = List(1,2,3,4,5) >>> a.reverseKGroup(2) [2->1->4->3->5->None] >>> a.reverseKGroup(3) [3->2->1->4->5->None] >>> b = List(range(1,11)) >>> for i in range(1,8): b.reverseKGroup(i) [1->2->3->4->5->6->7->8->9->10->None] [2->1->4->3->6->5->8->7->10->9->None] [3->2->1->6->5->4->9->8->7->10->None] [4->3->2->1->8->7->6->5->9->10->None] [5->4->3->2->1->10->9->8->7->6->None] [6->5->4->3->2->1->7->8->9->10->None] [7->6->5->4->3->2->1->8->9->10->None] >>>
7. 链表旋转
Rotate List (#61)
给定一个链表,将列表向右旋转k个节点,其中k为非负整数。
示例1
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
示例2
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
def rotateList(self,k): node1,node2,ptr = Node(),Node(),self.head length = self.size() k %= length if not k: return self head,tail = node1,node2 for i in range(length-k): head.next = Node(ptr.val) head,ptr = head.next,ptr.next while ptr: tail.next = Node(ptr.val) tail,ptr = tail.next,ptr.next tail.next = node1.next return List(node2.next)
>>> a = List(1,2,3,4,5) >>> a.rotateList(1) [5->1->2->3->4->None] >>> a.rotateList(2) [4->5->1->2->3->None] >>> b = List(0,1,2) >>> for i in range(1,5): b.rotateList(i) [2->0->1->None] [1->2->0->None] [0->1->2->None] [2->0->1->None] >>>
直接调用已定义的基本方法.rotate()或者重载的右移运算也能完成任务:
>>> list1 = List(range(1,6)) >>> list1.rotate(-1) [5->1->2->3->4->None] >>> list1.rotate(-2) [4->5->1->2->3->None] >>> list1 [1->2->3->4->5->None] >>> list1>>2 [4->5->1->2->3->None] >>> list1 [4->5->1->2->3->None] >>> >>> list2 = List(0,1,2) >>> k = 4 >>> for i in range(1,k+1): print(list2.rotate(-i)) [2->0->1->None] [1->2->0->None] [0->1->2->None] [2->0->1->None] >>> list2 [0->1->2->None] >>> list2 >> k [2->0->1->None] >>> list2 [2->0->1->None] >>>
8. 删除重复节点Ⅰ
Remove Duplicates from Sorted List (#82)
给定一个已排序链表,删除重复节点,原始链表中多次出现的数字只能保留一次。
示例
输入: 1->1->2
输出: 1->2
输入: 1->1->2->3->3
输出: 1->2->3
def deleteDup(self): ret = List() head,ptr = self.head,ret.head while head: if head.val!=ptr.val: ptr.next = Node(head.val) ptr = ptr.next head = head.next return List(ret.head.next)
>>> list1 = List(1,1,2) >>> list1.deleteDup() [1->2->None] >>> list2 = List(1,1,2,3,3) >>> list2.deleteDup() [1->2->3->None] >>> >>> list3 = List(1,2,3,3,4,4,4,5) >>> list3.deleteDup() [1->2->3->4->5->None]
9. 删除重复节点Ⅱ
Remove Duplicates from Sorted List (#83)
给定一个排序链表,删除所有重复的节点,留原始链表有过重复的数字一个也不留。
示例
输入: 1->2->3->3->4->4->5
输出: 1->2->5
输入: 1->1->1->2->3
输出: 2->3
def removeDup(self): ret = List() ptr1,ptr2 = self.head,ret.head if not ptr1.next: return self if ptr1.val!=ptr1.next.val: ptr2.next = Node(ptr1.val) ptr2 = ptr2.next t,ptr1 = ptr1.val,ptr1.next while ptr1.next: if t!=ptr1.val!=ptr1.next.val: ptr2.next = Node(ptr1.val) ptr2 = ptr2.next t = ptr1.val ptr1 = ptr1.next if t!=ptr1.val: ptr2.next = Node(ptr1.val) return List(ret.head.next)
>>> list1 = List(1,2,3,3,4,4,5) >>> list1.removeDup() [1->2->5->None] >>> list2 = List(1,1,1,2,3) >>> list2.removeDup() [2->3->None] >>> list3 = List(1,2,3,3) >>> list3.removeDup() [1->2->None]