LinkList

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

单链表

链表结构

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
class LinkList:
    def __init__(self):
        self.head = None

    def pushFront(self, ele):
        # 头插入
        node = Node(ele)
        node.next = self.head
        self.head = node

    def popFront(self):
        # 头删除
        if self.head is None:
            return
        self.head = self.head.next
        
    def show(self):
        cur = self.head
        while cur:
            print(cur.val)
            cur = cur.next

链表遍历

链表插入时间复杂度是O(1),但是查找却是O(N)

链表反转

    def reverse(self):
        if self.head is None:
            return
        cur = self.head
        pre = None
        while cur:
            pre, cur.next, cur = cur, pre, cur.next

        self.head = pre

递归写法

class Solution:
    def reverse(self, root: Node) -> Node:
        def recursion(prev: Node, cur: Node):
            if not cur:
                return prev
            nextNode = cur.next
            cur.next = prev
            prev = cur
            return recursion(prev, nextNode)

        prev = None
        cur = root

        return recursion(prev, cur)

链表合并

两个链表合并

def merge(linkA, linkB: Node) -> Node:
    if linkA is None:
        return linkB
    if linkB is None:
        return linkA
    link = None
    if linkA.val < linkB.val:
        link = linkA
        link.next = mergeLink(linkA.next, linkB)
    else:
        link = linkB
        link.next = mergeLink(linkA, linkB.next)
    return link

链表排序

这里列举一种归并排序

def merge_sort(head: Node) -> Node:
    if head is None or head.next is None:
        return head
    slow = head
    fast = head
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next

    left = head
    right = slow.next
    slow.next = None
    l = merge_sort(left)
    r = merge_sort(right)
    return merge(l, r)

双链表

双链表比起单链表多了个prev指向前一个节点

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

算法

链表有环

判断单链表是否有环

声明两个指针，一个是慢指针，每次走一步，一个是快指针，每次走两步
从链表头到环节点，距离为a，环的长度为R，相遇点到环节点的距离为x，慢指针走了a+x的距离，快指针走了a+x+nR(n为圈数)，慢指针*2=快指针，可以得出2(a+x)=a+x+nR, a = nR-x
定义两个指针，分别从头部和slow出发，相遇的点就是环入口

class Solution:
    def find_circle(self, head: Node):
        # 返回链表有环的点
        slow = head
        fast = head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                break
        if fast.next is None:
            # 无环
            return None
        cur = head
        while slow:
            if cur == slow:
                break
            cur = cur.next
            slow = slow.next

        return cur

LRU

用hash表和链表可以实现一个简单的LRU

class LRU:
    def __init__(self, capacity=10):
        '''index存储key对应的Node的Pre信息；head存储实际的链表'''
        self.index = {}
        # 初始化head节点
        self.head = Node(-1, -1)
        self.tail = self.head
        self.capacity = capacity

    def put(self, key, val):
        if self.get(key) != -1:
            self.index[key].next.val = val
            return
        node = Node(key, val)
        self.index[node.key] = self.tail
        self.moveToTail(node)
        if self.size() > self.capacity:
            self.evict()

    def get(self, key):
        if key not in self.index:
            return -1

        pre = self.index[key]
        cur = pre.next
        if cur != self.tail:
            pre.next = cur.next
            self.index[cur.next.key] = pre
            self.index[cur.key] = self.tail
            self.moveToTail(cur)
        return cur.val

    def moveToTail(self, node: Node):
        node.next = None
        self.tail.next = node
        self.tail = self.tail.next

    def evict(self):
        head = self.head
        # head头节点是Node(-1, -1)
        del self.index[head.next.key]
        self.index[head.next.next.key] = self.head
        self.head.next = self.head.next.next

    def size(self):
        return len(self.index)