链表：(链表应用：操作系统的缓存、Dictionary)
1. 链表由一系列数据记录构成，在每个记录里有个区域包含一个指向下一个数据记录的索引
2. 链表vs数组列表
（1）使用固定步数的操作可以在列表中任意节点做插入、删除操作
（2）不允许随机访问
3. 循环链表和双向链表
4. 哨兵节点
在某些实现中，可能会在第一个数据记录之前或者最后一个数据记录之后添加一个额外的哨兵节点或者哑元节点
简化和加快一些列表处理的算法
链表vs.动态数组
都需要动态分配内存块
动态数组：
通过索引访问和分配非常快速，时间复杂度为O(1)
添加元素（插入到数组的末尾）相对比较快，平摊时间复杂度为O(1)
在动态数组里的任意位置添加和删除节点会很慢，时间复杂度为O(n)
当需要对插入和删除做调整时，可能会出现不可预知的表现。
会有一些未使用的空间
链表：
在列表中的任意位置做插入和删除都很快，时间复杂度为O(1)
索引访问(随机访问)慢，时间复杂度为O(n)
5. 抽象数据类型（ADT）列表操作
（1）创建一个空列表
（2）判断列表是否为空
（3）确定列表中元素个数
（4）在列表中给定位置添加一个元素
（5）在列表中给定位置删除一个元素
（6）删除列表中所有元素
（7）在列表中取到给定位置上的元素
（8）每一项操作的时间复杂度
class Node: def __init__(self, value = None, next = None): self.value = value self.next = next class LinkedList: def __init__(self): self.head = Node(None, None) self.size = 0 def get_first(self): if not self.head.next: print('LinkedList is empty') return self.head.next def get_last(self): if not self.head.next: print('LinkedList is empty') node = self.head while node.next != None: node = node.next return node def get(self, index): if (index < 0 or index >= self.length): print('index is out of bound'); if not self.head.next: print('LinkedList is empty') node = self.head.next for i in range(index): node = node.next return node def add_first(self, value): node = Node(value, None) node.next = self.head.next self.head.next = node self.size += 1 def add_last(self, value): new_node = Node(value,None) node = self.head while node.next != None: node = node.next node.next = new_node self.size += 1 def remove_first(self): if not self.head.next: print("the linked list is empty") value = self.head.next self.head.next = self.head.next.next self.size -= 1 return value def remove_last(self): if not self.head.next: print("the linked list is empty") node = self.head.next pre = self.head while node.next != None: pre = node node = node.next pre.next = None self.size -= 1 return node.value def add(self, index, value): if (index < 0 or index > self.size): print('index is out of bound') if not self.head.next: print('LinkedList is empty') new_node = Node(value) node = self.head for i in range(index): node = node.next new_node.next = node.next; node.next = new_node; self.size += 1 def remove(self, index): if (index < 0 or index >= self.size): print('index is out of bound'); if not self.head.next: print("the linked list is empty") node = self.head for i in range(index): node = node.next result = node.next node.next = node.next.next self.size -= 1 return result def print_list(self): node = self.head while node.next != None: node = node.next print(node.value, end = " ") print() def length(self): return self.size ll = LinkedList() ll.add_first(5) ll.add(1,8) ll.add_last(14) print(ll.length()) ll.print_list()
6. 练习1：删除链表中的节点，除了结尾，只允许访问那个节点
def delete_node(node): print(node.value) node.value = node.next.value node.next = node.next.next
7. 练习2：找到中间节点
def find_middle(lst): assert lst.head is not None and lst.head.next is not None head = lst.head fast = head slow = head while fast is not None and fast.next is not None: fast = fast.next.next slow = slow.next return slow.value
8. 练习3：是否有环
def has_cycle(lst): return has_cycle_helper(lst.head) def has_cycle_helper(head): if head is None: return False slow = head fast = head while fast is not None and fast.next is not None: fast = fast.next.next slow = slow.next if slow==fast: return True return False
9. 练习4：找到环的开始：先跑两遍，一个快的是两倍速一个慢是一倍速，两者相遇后，将快的重归于原点，慢的继续跑，两个再同样速度跑，相遇就是环的起点
def find_beginning(head): if head is None: return None slow = head fast = head while fast is not None and fast.next is not None: fast = fast.next.next slow = slow.next if slow==fast: fast = head break if fast is None or fast.next is None: return None while fast != slow: fast = fast.next slow = slow.next return slow
9. 练习5：删除倒数第N个节点（限制：不能用size）
def remove_nth(lst, n): assert n<=lst.length and n > 0 fast = lst.head while n>0: fast = fast.next n = n - 1 slow = lst.head while fast.next is not None: fast = fast.next slow = slow.next result = slow.next slow.next = slow.next.next lst.length = lst.length - 1 return result
10. 练习6：分半：给定一个列表，把它分成两个列表，一个是前半部分，一个是后半部分
def split(head): if (head is None): return slow = head fast = head front_last_node = slow while (fast is not None): front_last_node = slow slow = slow.next fast = fast.next.next if fast.next is not None else None front_last_node.next = None front = head back = slow return (front, back)
11. 练习7：合并两个排序链表
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
def mergeTwoLists1(l1, l2): dummy = cur = Node(0) while l1 and l2: if l1.value < l2.value: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 or l2 return dummy.next
def mergeTwoLists2(l1, l2): if not l1 or not l2: return l1 or l2 if l1.value < l2.value: l1.next = mergeTwoLists2(l1.next, l2) return l1 else: l2.next = mergeTwoLists2(l1, l2.next) return l2
练习8：
找到两个相同链表的起始位置
A: a1 → a2
↘
c1 → c2 → c3
↗ B: b1 → b2 → b3
. 题解：先让AB同时跑，A先到终点，然后让A从B开始的位置再跑，B到终点后从A开始的位置继续跑，两者到达C1相遇
def getIntersectionNode2(headA, headB): if headA and headB: A, B = headA, headB while A!=B: A = A.next if A else headB B = B.next if B else headA return A
练习9：排序一个链表O（nlgn）
先找到中点，然后将一个链表拆分为两个链表，然后将每一个链表排序合并
def sortList(head): if head is None or head.next is None: return head mid = getMiddle(head) rHead = mid.next mid.next = None return merge(sortList(head), sortList(rHead)) def merge(lHead, rHead): dummyNode = dummyHead = Node(0) while lHead and rHead: if lHead.value < rHead.value: dummyHead.next = lHead lHead = lHead.next else: dummyHead.next = rHead rHead = rHead.next dummyHead = dummyHead.next if lHead: dummyHead.next = lHead elif rHead: dummyHead.next = rHead return dummyNode.next def getMiddle(head): if head is None: return head slow = head fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow
练习10：Partition 链表
给一个变量x, 链表左边所有的元素都比x小，x值右边所有元素值都比x大
def partition(head, x): left_head = Node(None) # head of the list with nodes values < x right_head = Node(None) # head of the list with nodes values >= x left = left_head # attach here nodes with values < x right = right_head # attach here nodes with values >= x # traverse the list and attach current node to left or right nodes while head: if head.value < x: left.next = head left = left.next else: # head.val >= x right.next = head right = right.next head = head.next right.next = None # set tail of the right list to None left.next = right_head.next # attach left list to the right return left_head.next # head of a new partitioned list
练习11：反转一个链表
def reverse(lst): head = lst.head result = None current = head.next nxt = None while current is not None: nxt = current.next current.next = result result = current current = nxt head.next = result
def reverseRecursion(node): if (node is None or node.next is None): return node p = reverseRecursion(node.next) node.next.next = node node.next = None return p