１０. 链表分组
Partition List （#86）
给定一个链表和一个整数，把链表分成“小于指定数”和“不小于指定数”的二组连接在一起，并且各组元素在本组中的先后位置保持与原链表相同。
示例
输入: 1->4->3->2->5->2->None, x = 3
输出: 1->2->2->4->3->5->None
def partition(self,x): if not self.head.next: return self gt,lt = Node(),Node() ptr1,ptr2,ptr = gt,lt,self.head while ptr: if ptr.val<x: ptr1.next = Node(ptr.val) ptr1 = ptr1.next else: ptr2.next = Node(ptr.val) ptr2 = ptr2.next ptr = ptr.next ptr1.next = lt.next return List(gt.next)
>>> list1 = List(1,4,3,2,5,2); x = 3 >>> list1.partition(x) [1->2->2->4->3->5->None] >>>
１１. 反转链表中一段节点
Reverse Linked List (a part of NodeList) (#92)
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
示例
输入: 1->2->3->4->5->None, m = 2, n = 4
输出: 1->4->3->2->5->None
１２. 重排链表
Reorder List (#143)
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list's nodes, only nodes itself may be changed.
给定一个链表，不允许修改数据域，按“从头尾向中间的顺序“重排节点。
示例
Given 1->2->3->4, reorder it to 1->4->2->3.
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
方法一：先遍历出长度和倒序链表，然后把两个链表的前半部分混插。
def reorder(self): if not self.head.next: return self size,tmp,ptr = 0,Node(),self.head while ptr: size += 1 tmp = Node(ptr.val,tmp) ptr = ptr.next ret = Node() ptr1,ptr2,ptr = self.head,tmp,ret for _ in range(size//2): ptr.next = Node(ptr1.val) ptr,ptr1 = ptr.next,ptr1.next ptr.next = Node(ptr2.val) ptr,ptr2 = ptr.next,ptr2.next if size%2: ptr.next = Node(ptr1.val) return List(ret.next)
>>> a = List(*range(1,5)) >>> a.reorder() [1->4->2->3->None] >>> b = List(*range(1,6)) >>> b.reorder() [1->5->2->4->3->None] >>> c = List(*range(1,7)) >>> c.reorder() [1->6->2->5->3->4->None] >>>
方法二：使用基本方法中的pophead(),poptail()反复弹出头尾节点，用弹出值新建一个链表。
def reorderHT(self): if not self.head.next or not self.head.next.next: return self ret,self = Node(),List(self) ptr = ret while self: ptr.next = Node(self.pophead()) ptr = ptr.next try: ptr.next = Node(self.poptail()) except: break ptr = ptr.next return List(ret.next)
>>> a = List(1,2,3,4) >>> a.reorderHT() [1->4->2->3->None] >>> b = List(1,2,3,4,5) >>> b.reorderHT() [1->5->2->4->3->None] >>> c = List(1,2,3,4,5,6) >>> c.reorderHT() [1->6->2->5->3->4->None] >>> c [1->2->3->4->5->6->None] >>>
１３. 链表插入排序
Insertion Sort List (#147)
Sort a linked list using insertion sort.
示例
输入: 4->2->1->3
输出: 1->2->3->4
输入: -1->5->3->4->0
输出: -1->0->3->4->5
已定义的基本方法中sorted(),sort()已能实现排序功能，但是排序时直接比较数据域的。
>>> list1 = List(6,3,4,5,2,1) >>> list1.sorted() [1->2->3->4->5->6->None] >>> list1 [6->3->4->5->2->1->None] >>> list1.sort() [1->2->3->4->5->6->None] >>> list1 [1->2->3->4->5->6->None] >>>
插入排序：
def insertionSort(self): if not self.head.next: return self ret = Node() ptr,ptr1 = List(self).head,ret while ptr: Next = ptr.next while ptr1.next and ptr1.next.val<ptr.val: ptr1 = ptr1.next ptr.next,ptr1.next = ptr1.next,ptr ptr,ptr1 = Next,ret return List(ret.next)
>>> list1 = List(4,2,1,3) >>> list1.insertionSort() [1->2->3->4->None] >>> list1 [4->2->1->3->None] >>> list2 = List(-1,5,3,4,0) >>> list2.insertionSort() [-1->0->3->4->5->None] >>> list2 [-1->5->3->4->0->None] >>>
１４. 链表归并排序
Sort List (#148)
Sort a linked list in O(n log n) time using constant space complexity.
归并排序： 时间复杂度 O(n log n)，空间复杂度 O(1)
１５. 删除指定值的所有节点
Remove Linked List Elements (#203)
删除给定链表中所有数值域等于指定值val的节点。
示例
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
def removeValues(self,val): if not self.head: return self ret = Node() ptr1,ptr2 = ret,self.head while ptr2: if ptr2.val!=val: ptr1.next = Node(ptr2.val) ptr1 = ptr1.next ptr2 = ptr2.next return List(ret.next)
>>> list1 = List(1,2,6,3,4,5,6); val = 6 >>> list1.removeValues(val) [1->2->3->4->5->None] >>> list1.removeValues(0) [1->2->6->3->4->5->6->None] >>>
方法二：迭代法
def removeElements(self,val): if isinstance(self,List): self = List(self.head.next) if self.head.val==val else List(self.head) self = self.head while self and self.val==val: self = self.next if self: self.next = List.removeElements(self.next,val) return self
>>> list1 = List(1,2,6,3,4,5,6); val = 6 >>> list1.removeElements(val) 1->2->3->4->5->None >>> list1 [1->2->6->3->4->5->6->None] >>> list2 = List(3,1,2,3,3,4,3,5,5,3); val = 3 >>> list2.removeElements(val) 1->2->4->5->5->None >>> list2 [3->1->2->3->3->4->3->5->5->3->None] >>>
１６. 反转链表
Reverse Linked List (#206)
Reverse a singly linked list.
链表的全部反转，这是很基础的方法。上面的第6题、第11题中已有部分的反转。
已定义的基本方法中已有 __reversed__、.reverse() 可以完成反转，把它们的代码稍作改进，相当于直接改变链表的指针方向，而不是用Node()嵌套新建一个链表，本质是一样的。
def reverseList(self): ret,ptr = None,self.head while ptr: ptr.next,ret,ptr = ret,ptr,ptr.next self.head = ret return self
>>> a = List(range(1,6)) >>> a.reverseList() [5->4->3->2->1->None] >>> b = List(range(0,10,2)) >>> b.reverseList() [8->6->4->2->0->None] >>> c = List(1) >>> c.reverseList() [1->None] >>> d = List() >>> d.reverseList() [None->None] >>> b = List(range(0,9,2)) >>> b.reverseList() [8->6->4->2->0->None] >>> b = List(range(0,3,2)) >>> b.reverseList() [2->0->None] >>>
１７. 回文链表
Palindrome Linked List (#234)
判断给定链表是否为回文链表，即链表与反转后的一致。
示例
Input: 1->2 Output: False Input: 1->2->2->1 Output: True
def isPalindrome(self): if not self.head.next: return True ptr,tmp = self.head,[] while ptr: tmp.append(ptr.val) ptr = ptr.next ptr = self.head while ptr: if ptr.val!=tmp.pop(): return False ptr = ptr.next return True
>>> list1 = List(1,2) >>> list1.isPalindrome() False >>> list2 = List(1,2,2,1) >>> list2.isPalindrome() True >>> list3 = List(1,2,3,2,1) >>> List.isPalindrome(list3) True >>>
直接调用已定义的基本方法__reversed__、__eq__、__contains__也能办到：
>>> list1 = List(1,2) >>> list1 in reversed(list1) False >>> list1 == reversed(list1) False >>> list2 = List(1,2,2,1) >>> list2 in reversed(list2) True >>> list2 == reversed(list2) True >>>
１８. 删除指定节点
Delete Node in a Linked List (#237)
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Given linked list -- head = [4,5,1,9], which looks like following: Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function. Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function. Note: The linked list will have at least two elements. All of the nodes' values will be unique. The given node will not be the tail and it will always be a valid node of the linked list. Do not return anything from your function.
与15题类同但只删除一个，如果不像Note中说明的一样：节点的值都是唯一的；那么还延用15题的方法则需要设置一个标记：重复的只不复制第一个。
def removeVal1(self,val): if not self.head: return self ret,flag = Node(),True ptr1,ptr2 = ret,self.head while ptr2: if flag and ptr2.val==val: flag = False else: ptr1.next = Node(ptr2.val) ptr1 = ptr1.next ptr2 = ptr2.next return List(ret.next)
>>> list1 = List(4,5,1,9); val = 5 >>> list1.removeVal1(val) [4->1->9->None] >>> list1.removeVal1(1) [4->5->9->None] >>> list2 = List(1,2,6,3,4,5,6); val = 6 >>> list2.removeVal1(val) [1->2->3->4->5->6->None] >>>
方法二：遇到指定值，直接跳指下一个节点，self的值会被变更。
def removeVal2(self,val): if not self.head: return self if self.head.val==val: self.head = self.head.next else: ptr = self.head while ptr.next: if ptr.next.val==val: ptr.next = ptr.next.next break ptr = ptr.next self.head = self.head or Node() return self
>>> list1 = List(4,5,1,9); val = 5 >>> list1.removeVal2(val) [4->1->9->None] >>> list1.removeVal2(1) [4->9->None] >>> list2 = List(1,2,6,3,4,5,6); val = 6 >>> list2.removeVal2(val) [1->2->3->4->5->6->None] >>> list2.removeVal2(6) [1->2->3->4->5->None] >>> list2.removeVal2(1) [2->3->4->5->None] >>>
直接调用已定义的基本方法.find()和.delete()也可完成：
>>> list1 = List(4,5,1,9); val = 5 >>> list1.delete(list1.find(val)) [4->1->9->None] >>> list1.delete(list1.find(1)) [4->9->None] >>> list2 = List(1,2,6,3,4,5,6); val = 6 >>> list2.delete(list2.find(val)) [1->2->3->4->5->6->None] >>> list2.delete(list2.find(val)) [1->2->3->4->5->None] >>> list2.delete(list2.find(1)) [2->3->4->5->None] >>>
１９. 奇偶索引重排
Odd Even Linked List (#328)
给定一个单链表，按节点索引号的奇偶重新排列。
示例
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
def oddevenIndex(self): if not self.head.next: return self odd,even,index = Node(),Node(),0 ptr1,ptr2,ptr = odd,even,self.head while ptr: index += 1 if index%2: ptr1.next = Node(ptr.val) ptr1 = ptr1.next else: ptr2.next = Node(ptr.val) ptr2 = ptr2.next ptr = ptr.next ptr1.next = even.next return List(odd.next)
>>> a = List(*range(1,6)) >>> a.oddevenIndex() [1->3->5->2->4->None] >>> b = List(2,1,3,5,6,4,7) >>> b.oddevenIndex() [2->3->6->7->1->5->4->None] >>>
类似题目：给定一个单链表，按节点数值域的奇偶重新排列。这类按要求分组的都与第10题属于同一类型。
def oddevenNumber(self): if not self.head.next: return self odd,even = Node(),Node() ptr1,ptr2,ptr = odd,even,self.head while ptr: if ptr.val%2: ptr1.next = Node(ptr.val) ptr1 = ptr1.next else: ptr2.next = Node(ptr.val) ptr2 = ptr2.next ptr = ptr.next ptr1.next = even.next return List(odd.next)
>>> a = List(*range(1,6)) >>> a.oddevenNumber() [1->3->5->2->4->None] >>> b = List(2,1,3,5,6,4,7) >>> b.oddevenNumber() [1->3->5->7->2->6->4->None] >>>
２０. 两数之和 II
Add Two Numbers II (#445)
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
第一题的变形，本题的链表是正序表示两个整数的非空链表，不允许反转完成加法。
示例
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
def Add2NumII(self,node): len1,len2 = self.size(),node.size() ret1,ret2,self = [],[],List(self.head) if len1>len2: ptr1,ptr2 = self.head,node.head else: ptr1,ptr2 = node.head,self.head len1,len2 = len2,len1 for _ in range(len1-len2): ret1.append(ptr1.val) ret2.append(0) ptr1 = ptr1.next while ptr2: ret1.append(ptr1.val) ret2.append(ptr2.val) ptr1,ptr2 = ptr1.next,ptr2.next ret,carry = Node(),0 for _ in range(len1): Sum = carry + ret1.pop() + ret2.pop() carry,Sum = divmod(Sum,10) ret = Node(Sum,ret) if carry: ret = Node(1,ret) return ret
>>> list1 = List(7,2,4,3); list2 = List(5,6,4) >>> list1.Add2NumII(list2) 7->8->0->7->None >>> list2.Add2NumII(list1) 7->8->0->7->None >>> list1 = List(5,2,0,8); list2 = List(9,5,5,3,3) >>> list1.Add2NumII(list2) 1->0->0->7->4->1->None >>> list2.Add2NumII(list1) 1->0->0->7->4->1->None >>>
２１ . 链表类设计
Design Linked List (#707)
Design your implementation of the linked list. You can choose to use the singly linked list or the
doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the
value of the current node, and next is a pointer/reference to the next node. If you want to use the
doubly linked list, you will need one more attribute prev to indicate the previous node in the
linked list. Assume all nodes in the linked list are 0-indexed.
Implement these functions in your linked list class:
get(index) : Get the value of the index-th node in the linked list. If the index is invalid, return -1.
addAtHead(val) : Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
addAtTail(val) : Append a node of value val to the last element of the linked list.
addAtIndex(index, val) : Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
deleteAtIndex(index) : Delete the index-th node in the linked list, if the index is valid.
Example: MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 linkedList.get(1); // returns 2 linkedList.deleteAtIndex(1); // now the linked list is 1->3 linkedList.get(1); // returns 3
Example:
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 linkedList.get(1); // returns 2 linkedList.deleteAtIndex(1); // now the linked list is 1->3 linkedList.get(1); // returns 3
Note:
All values will be in the range of [1, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in LinkedList library.
类似的功能在已定义的基本方法中都有：
>>> linkedList = List(1) >>> linkedList.append(3) [1->3->None] >>> linkedList.insert(1,2) [1->2->3->None] >>> linkedList[1] 2 >>> linkedList.delete(1) [1->3->None] >>> linkedList[1] 3
２２ . 链表中间节点
Middle of the Linked List (#876)
Given a non-empty, singly linked list with head node head, return a middle node of linked list.
If there are two middle nodes, return the second middle node.
给定一个非空链表，返回中间节点。如有2个中间节点(节点数为偶数时)返回第2个。
方法一：先遍历出长度，再遍历一半长度
def middleNode(self): if not self.head.next: return self.head.val ptr,size = self.head,0 while ptr: size += 1 ptr = ptr.next ptr = self.head for _ in range(size//2): ptr = ptr.next return ptr.val
>>> list1 = List(range(1,6)) >>> list1 [1->2->3->4->5->None] >>> list1.middleNode() 3 >>> list2 = List(range(1,7)) >>> list2 [1->2->3->4->5->6->None] >>> list2.middleNode() 4 >>>
方法二：快指针步进2，慢指针步进1，当快指针移到尾部时，慢指针就在中间节点上。
def middleNodefs(self): if not self.head.next: return self.head.val fast,slow = self.head,self.head while fast: if fast.next is None: return slow.val fast,slow = fast.next,slow.next fast = fast.next return slow.val
>>> list1 = List(range(1,6)) >>> list1.middleNodefs() 3 >>> list1 = List(range(1,7)) >>> list1.middleNodefs() 4 >>>
２３ . 下一个大节点
Next Greater Node In Linked List (#1019)
We are given a linked list with head as the first node. Let's number the nodes in the list: node_1, node_2, node_3, ... etc.
Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.
Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).
Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.
找出链表中第一个比自己大的节点，没找到则为0。
示例
输入: [2,1,5]
输出: [5,5,0]
输入: [2,7,4,3,5]
输出: [7,0,5,5,0]
输入: [1,7,5,1,9,2,5,1]
输出: [7,9,9,9,0,5,0,0]
def nextGreaterNode(self): ret,ptr = [],self.head while ptr: cur,tmp = ptr,ptr.val while cur: if cur.val>tmp: ret.append(cur.val) break cur = cur.next else: ret.append(0) ptr = ptr.next return ret
>>> a = List([2,1,5]) >>> a.nextGreaterNode() [5, 5, 0] >>> b = List([2,7,4,3,5]) >>> b.nextGreaterNode() [7, 0, 5, 5, 0] >>> c = List([1,7,5,1,9,2,5,1]) >>> c.nextGreaterNode() [7, 9, 9, 9, 0, 5, 0, 0] >>>
