参考链接：https://github.com/itcharge/LeetCode-Py

一、链表基础知识

1.1 链表简介

链表（Linked List）：是一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。
简单来说，链表 是实现线性表的链式存储结构的基础。

链表结构优缺点：

• 优点：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比数组高（插入、移动、删除元素等）。
• 缺点：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链表结构比数组结构的空间开销大。

链表种类：

• 单链表。单链表通过将一组任意的存储单元串联在一起。其中，每个数据元素占用若干存储单元的组合称为一个「链节点」。
• 双链表。它的每个链节点中有两个指针，分别指向直接后继和直接前驱。
• 循环链表。它的最后一个链节点指向头节点，形成一个环。

1.2 链表的基本操作

1.2.1 链表的结构定义

• 链表是由链节点通过 next 链接而构成的，所以先来定义一个简单的链节点类，即ListNode 类。ListNode 类使用成员变量 val 表示数据元素的值，使用指针变量 next 表示后继指针。
• 然后再定义链表类，即 LinkedList 类。ListkedList 类中只有一个链节点变量 head 用来表示链表的头节点。

代码如下：

# 链节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 链表类
class LinkedList:
    def __init__(self):
        self.head = None

1.2.1 建立一个线性链表

建立一个线性链表就是根据线性表的数据元素动态生成链节点，并依次将其连接到链表中。其做法如下：

• 从所给线性表的第 1 个数据元素开始依次获取表中的数据元素。
• 每获取一个数据元素，就为该数据元素生成一个新节点，将新节点插入到链表的尾部。
• 插入完毕之后返回第 1 个链节点的地址。

建立一个线性链表的时间复杂度为 ，n 为线性表长度。
代码如下：

# 根据 data 初始化一个新链表
def create(self, data):
    self.head = ListNode(0)
    cur = self.head
    for i in range(len(data)):
        node = ListNode(data[i])
        cur.next = node
        cur = cur.next

1.2.3 求线性链表的长度

线性链表的长度被定义为链表中包含的链节点的个数。求线性链表的长度操作只需要使用一个可以顺着链表指针移动的指针变量 cur 和一个计数器 count。具体做法如下：

• 让指针变量 cur 指向链表的第 1 个链节点。
• 然后顺着链节点的 next 指针遍历链表，指针变量 cur 每指向一个链节点，计数器就做一次计数。
• 等 cur 指向为空时结束遍历，此时计数器的数值就是链表的长度，将其返回即可。

求线性链表的长度操作的问题规模是链表的链节点数 n，基本操作是 cur 指针的移动，操作的次数为 n，因此算法的时间复杂度为 。
代码如下：

# 获取链表长度
def length(self):
    count = 0
    cur = self.head
    while cur:
        count += 1
        cur = cur.next 
    return count

1.2.4 查找元素

在链表中查找值为 val 的位置：链表不能像数组那样进行随机访问，只能从头节点 head 开始，沿着链表一个一个节点逐一进行查找。如果查找成功，返回被查找节点的地址。否则返回 None。

查找元素操作的问题规模是链表的长度 n，而基本操作是指针 cur 的移动操作，所以查找元素算法的时间复杂度为 。

# 查找元素
def find(self, val):
    cur = self.head
    while cur:
        if val == cur.val:
            return cur
        cur = cur.next

    return None

1.2.5 插入元素

链表中插入元素操作分为三种：

• 链表头部插入元素：在链表第 1 个链节点之前插入值为 val 的链节点。
• 链表尾部插入元素：在链表最后 1 个链节点之后插入值为 val 的链节点。
• 链表中间插入元素：在链表第 i 个链节点之前插入值为 val 的链节点。

链表头部插入元素
算法实现的步骤如下：

• 先创建一个值为 val 的链节点 node。
• 然后将 node 的 next 指针指向链表的头节点 head。

• 再将链表的头节点 head 指向 node。

  
  
  image.png

因为在链表头部插入链节点与链表的长度无关，所以该算法的时间复杂度为 。

# 头部插入元素
def insertFront(self, val):
    node = ListNode(val)
    node.next = self.head
    self.head = node

尾部插入元素
算法实现的步骤如下：

• 先创建一个值为 val 的链节点 node。
• 使用指针 cur 指向链表的头节点 head。
• 通过链节点的 next 指针移动 cur 指针，从而遍历链表，直到 cur.next == None。
• 令 cur.next 指向将新的链节点 node。
  
  image.png
  
  因为将 cur 从链表头部移动到尾部的操作次数是 n 次，所以该算法的时间复杂度是 。

# 尾部插入元素
def insertRear(self, val):
    node = ListNode(val)
    cur = self.head
    while cur.next:
        cur = cur.next
    cur.next = node

中间插入元素
算法的实现步骤如下：

• 使用指针变量 cur 和一个计数器 count。令 cur 指向链表的头节点，count 初始值赋值为 0。
• 沿着链节点的 next 指针遍历链表，指针变量 cur 每指向一个链节点，计数器就做一次计数。
• 当 count == index - 1 时，说明遍历到了第 index - 1 个链节点，此时停止遍历。
• 创建一个值为 val 的链节点 node。
• 将 node.next 指向 cur.next。
• 然后令 cur.next 指向 node。
  
  image.png
  
  因为将 cur 从链表头部移动到第 i 个链节点之前的操作平均时间复杂度是 ，所以该算法的时间复杂度是 。

# 中间插入元素
def insertInside(self, index, val):
    count = 0
    cur = self.head
    while cur and count < index - 1:
        count += 1
        cur = cur.next
        
    if not cur:
        return 'Error'
    
    node = ListNode(val)
    node.next = cur.next
    cur.next = node

1.2.6 改变元素

将链表中第 i 个元素值改为 val：首先要先遍历到第 i 个链节点，然后直接更改第 i 个链节点的元素值。具体做法如下：

• 使用指针变量 cur 和一个计数器 count。令 cur 指向链表的头节点，count 初始值赋值为 0。
• 沿着链节点的 next 指针遍历链表，指针变量 cur 每指向一个链节点，计数器就做一次计数。
• 当 count == index 时，说明遍历到了第 index 个链节点，此时停止遍历。
• 直接更改 cur 的值 val。

因为将 cur 从链表头部移动到第 i 个链节点的操作平均时间复杂度是 ，所以该算法的时间复杂度是 。

# 改变元素
def change(self, index, val):
    count = 0
    cur = self.head
    while cur and count < index:
        count += 1
        cur = cur.next
        
    if not cur:
        return 'Error'
    
    cur.val = val

1.2.7 删除元素

链表的删除元素操作同样分为三种情况：

• 链表头部删除元素：删除链表的第 1 个链节点。
• 链表尾部删除元素：删除链表末尾最后 1 个链节点。
• 链表中间删除元素：删除链表第 i 个链节点。

二、链表排序

2.1 链表冒泡排序

算法描述：
使用三个指针 node_i、node_j 和 tail。其中 node_i 用于控制外循环次数，循环次数为链节点个数（链表长度）。node_j 和 tail 用于控制内循环次数和循环结束位置。
算法步骤：

• 排序开始前，将 node_i 、node_j 置于头节点位置。tail 指向链表末尾，即 None。
• 比较链表中相邻两个元素 node_j.val 与 node_j.next.val 的值大小，如果 node_j.val > node_j.next.val，则值相互交换。否则不发生交换。然后向右移动 node_j 指针，直到 node_j.next == tail 时停止。
• 一次循环之后，将 tail 移动到 node_j 所在位置。相当于 tail 向左移动了一位。此时 tail 节点右侧为链表中最大的链节点。
• 然后移动 node_i 节点，并将 node_j 置于头节点位置。然后重复第 3、4 步操作。
• 直到 node_i 节点移动到链表末尾停止，排序结束。
• 返回链表的头节点 head。

def bubbleSort(self, head: ListNode):
    node_i = head
    tail = None
    # 外层循环次数为 链表节点个数
    while node_i:
        node_j = head
        while node_j and node_j.next != tail:
            if node_j.val > node_j.next.val:
                # 交换两个节点的值
                node_j.val, node_j.next.val = node_j.next.val, node_j.val
            node_j = node_j.next
        # 尾指针向前移动 1 位，此时尾指针右侧为排好序的链表
        tail = node_j
        node_i = node_i.next
        
    return head

2.2 链表选择排序

算法描述：

• 使用两个指针 node_i、node_j。node_i 既可以用于控制外循环次数，又可以作为当前未排序链表的第一个链节点位置。
• 使用 min_node 记录当前未排序链表中值最小的链节点。
• 每一趟排序开始时，先令 min_node = node_i（即暂时假设链表中 node_i 节点为值最小的节点，经过比较后再确定最小值节点位置）。
• 然后依次比较未排序链表中 node_j.val 与 min_node.val 的值大小。如果 node_j.val > min_node.val，则更新 min_node 为 node_j。
• 这一趟排序结束时，未排序链表中最小值节点为 min_node，如果 node_i != min_node，则将 node_i 与 min_node 值进行交换。如果 node_i == min_node，则不用交换。
• 排序结束后，继续向右移动 node_i，重复上述步骤，在剩余未排序链表中寻找最小的链节点，并与 node_i 进行比较和交换，直到 node_i == None 或者 node_i.next == None 时，停止排序。
• 返回链表的头节点 head。

def sectionSort(self, head: ListNode):
    node_i = head
    # node_i 为当前未排序链表的第一个链节点
    while node_i and node_i.next:
        # min_node 为未排序链表中的值最小节点
        min_node = node_i
        node_j = node_i.next
        while node_j:
            if node_j.val < min_node.val:
                min_node = node_j
            node_j = node_j.next
        # 交换值最小节点与未排序链表中第一个节点的值
        if node_i != min_node:
            node_i.val, min_node.val = min_node.val, node_i.val
        node_i = node_i.next
    
    return head

2.3 链表插入排序

算法描述：

• 1、先使用哑节点 dummy_head 构造一个指向 head 的指针，使得可以从 head 开始遍历。
• 2、维护 sorted_list 为链表的已排序部分的最后一个节点，初始时，sorted_list = head。
• 3、维护 prev 为插入元素位置的前一个节点，维护 cur 为待插入元素。初始时，prev = head，cur = head.next。
• 4、比较 sorted_list 和 cur 的节点值。
  • 如果 sorted_list.val <= cur.val，说明 cur 应该插入到 sorted_list 之后，则将 sorted_list 后移一位。
  • 如果 sorted_list.val > cur.val，说明 cur 应该插入到 head 与 sorted_list 之间。则使用 prev 从 head 开始遍历，直到找到插入 cur 的位置的前一个节点位置。然后将 cur 插入。
• 5、令 cur = sorted_list.next，此时 cur 为下一个待插入元素。
• 重复 4、5 步骤，直到 cur 遍历结束为空。返回 dummy_head 的下一个节点。

def insertionSort(self, head: ListNode):
    if not head and not head.next:
        return head
    
    dummy_head = ListNode(-1)
    dummy_head.next = head
    sorted_list = head
    cur = head.next 
    
    while cur:
        if sorted_list.val <= cur.val:
            # 将 cur 插入到 sorted_list 之后
            sorted_list = sorted_list.next 
        else:
            prev = dummy_head
            while prev.next.val <= cur.val:
                prev = prev.next
            # 将 cur 到链表中间
            sorted_list.next = cur.next
            cur.next = prev.next
            prev.next = cur
        cur = sorted_list.next 
    
    return dummy_head.next

2.4 链表归并排序

算法描述：
分割环节：找到链表中心链节点，从中心节点将链表断开，并递归进行分割。

• 使用快慢指针 fast = head.next、slow = head，让 fast 每次移动 2 步，slow 移动 1 步，移动到链表末尾，从而找到链表中心链节点，即 slow。
• 从中心位置将链表从中心位置分为左右两个链表 left_head 和 right_head，并从中心位置将其断开，即 slow.next = None。
• 对左右两个链表分别进行递归分割，直到每个链表中只包含一个链节点。

归并环节：将递归后的链表进行两两归并，完成一遍后每个子链表长度加倍。重复进行归并操作，直到得到完整的链表。

• 使用哑节点 dummy_head 构造一个头节点，并使用 cur 指向 dummy_head 用于遍历。
• 比较两个链表头节点 left 和 right 的值大小。将较小的头节点加入到合并后的链表中。并向后移动该链表的头节点指针。
• 然后重复上一步操作，直到两个链表中出现链表为空的情况。
• 将剩余链表插入到合并中的链表中。
• 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为合并后的头节点返回。

def merge(self, left, right):
    # 归并环节
    dummy_head = ListNode(-1)
    cur = dummy_head
    while left and right:
        if left.val <= right.val:
            cur.next = left
            left = left.next
        else:
            cur.next = right
            right = right.next
        cur = cur.next
    
    if left:
        cur.next = left
    elif right:
        cur.next = right
        
    return dummy_head.next
    
def mergeSort(self, head: ListNode):
    # 分割环节
    if not head or not head.next:
        return head
    
    # 快慢指针找到中心链节点
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next 
        fast = fast.next.next 
    
    # 断开左右链节点
    left_head, right_head = head, slow.next 
    slow.next = None
    
    # 归并操作
    return self.merge(self.mergeSort(left_head), self.mergeSort(right_head))

2.5 链表快速排序

算法描述：

• 从链表中找到一个基准值 pivot，这里以头节点为基准值。
• 然后通过快慢指针 node_i、node_j 在链表中移动，使得 node_i 之前的节点值都小于基准值，node_i 之后的节点值都大于基准值。从而把数组拆分为左右两个部分。
• 再对左右两个部分分别重复第二步，直到各个部分只有一个节点，则排序结束。

def partition(self, left: ListNode, right: ListNode):
    # 左闭右开，区间没有元素或者只有一个元素，直接返回第一个节点
    if left == right or left.next == right:
        return left
    # 选择头节点为基准节点
    pivot = left.val
    # 使用 node_i, node_j 双指针，保证 node_i 之前的节点值都小于基准节点值，node_i 与 node_j 之间的节点值都大于等于基准节点值
    node_i, node_j = left, left.next
    
    while node_j != right:
        # 当 node_j 的值小于基准节点值时，交换 node_i 与 node_j 的值
        if node_j.val < pivot:
            node_i = node_i.next
            node_i.val, node_j.val = node_j.val, node_i.val
        node_j = node_j.next
    # 将基准节点放到正确位置上
    node_i.val, left.val = left.val, node_i.val
    return node_i
    
def quickSort(self, left: ListNode, right: ListNode):
    if left == right or left.next == right:
        return left
    pi = self.partition(left, right)
    self.quickSort(left, pi)
    self.quickSort(pi.next, right)
    return left

2.7 链表计数排序

算法描述：

• 使用 cur 指针遍历一遍链表。找出链表中最大值 list_max 和最小值 list_min。
• 使用数组 counts 存储节点出现次数。
• 再次使用 cur 指针遍历一遍链表。将链表中每个值为 cur.val 的节点出现次数，存入数组对应第 cur.val - list_min 项中。
• 反向填充目标链表：
  • 建立一个哑节点 dummy_head，作为链表的头节点。使用 cur 指针指向 dummy_head。
• 从小到大遍历一遍数组 counts。对于每个 counts[i] != 0 的元素建立一个链节点，值为 i + list_min，将其插入到 cur.next 上。并向右移动 cur。同时 counts[i] -= 1。直到 counts[i] == 0 后继续向后遍历数组 counts。
• 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为新链表的头节点返回。

def countingSort(self, head: ListNode):
    if not head:
        return head
    
    # 找出链表中最大值 list_max 和最小值 list_min
    list_min, list_max = float('inf'), float('-inf')
    cur = head
    while cur:
        if cur.val < list_min:
            list_min = cur.val
        if cur.val > list_max:
            list_max = cur.val
        cur = cur.next
        
    size = list_max - list_min + 1
    counts = [0 for _ in range(size)]
    
    cur = head
    while cur:
        counts[cur.val - list_min] += 1
        cur = cur.next
        
    dummy_head = ListNode(-1)
    cur = dummy_head
    for i in range(size):
        while counts[i]:
            cur.next = ListNode(i + list_min)
            counts[i] -= 1
            cur = cur.next
    return dummy_head.nextv

2.7 链表桶排序

算法描述：

• 使用 cur 指针遍历一遍链表。找出链表中最大值 list_max 和最小值 list_min。
• 通过 (最大值 - 最小值) / 每个桶的大小 计算出桶的个数，即 bucket_count = (list_max - list_min) // bucket_size + 1 个桶。
• 定义二维数组 buckets 为桶，外层数组大小为 bucket_count 个。
• 使用 cur 指针再次遍历一遍链表，将每个元素装入对应的桶中。
• 对每个桶内的元素单独排序（使用插入、归并、快排等算法）。
• 最后按照顺序将桶内的元素拼成新的链表，并返回。

def insertionSort(self, arr):
    for i in range(1, len(arr)):
        temp = arr[i]
        j = i
        while j > 0 and arr[j - 1] > temp:
            arr[j] = arr[j - 1]
            j -= 1
        arr[j] = temp
        
    return arr

def bucketSort(self, head: ListNode, bucket_size=5):
    if not head:
        return head
    
    # 找出链表中最大值 list_max 和最小值 list_min
    list_min, list_max = float('inf'), float('-inf')
    cur = head
    while cur:
        if cur.val < list_min:
            list_min = cur.val
        if cur.val > list_max:
            list_max = cur.val
        cur = cur.next
        
    # 计算桶的个数，并定义桶
    bucket_count = (list_max - list_min) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]
    
    # 将链表节点值依次添加到对应桶中
    cur = head
    while cur:
        buckets[(cur.val - list_min) // bucket_size].append(cur.val)
        cur = cur.next
    
    dummy_head = ListNode(-1)
    cur = dummy_head
    for bucket in buckets:
        # 对桶中元素单独排序
        self.sortLinkedList(bucket)
        for num in bucket:
            cur.next = ListNode(num)
            cur = cur.next
    
    return dummy_head.next

2.8 链表基数排序

算法描述：

• 使用 cur 指针遍历链表，获取节点值位数最长的位数 size。
• 从个位到高位遍历位数。因为 0 ~ 9 共有 10 位数字，所以建立 10 个桶。
• 以每个节点对应位数上的数字为索引，将节点值放入到对应桶中。
  建立一个哑节点 dummy_head，作为链表的头节点。使用 cur 指针指向 dummy_head。
• 将桶中元素依次取出，并根据元素值建立链表节点，并插入到新的链表后面。从而生成新的链表。
• 之后依次以十位，百位，…，直到最大值元素的最高位处值为索引，放入到对应桶中，并生成新的链表，最终完成排序。
• 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为新链表的头节点返回。

def radixSort(self, head: ListNode):       
    # 计算位数最长的位数
    size = 0
    cur = head
    while cur:
        val_len = len(str(cur.val))
        if val_len > size:
            size = val_len
        cur = cur.next
    
    # 从个位到高位遍历位数
    for i in range(size):
        buckets = [[] for _ in range(10)]
        cur = head
        while cur:
            # 以每个节点对应位数上的数字为索引，将节点值放入到对应桶中
            buckets[cur.val // (10 ** i) % 10].append(cur.val)
            cur = cur.next
        
        # 生成新的链表
        dummy_head = ListNode(-1)
        cur = dummy_head
        for bucket in buckets:
            for num in bucket:
                cur.next = ListNode(num)
                cur = cur.next
        head = dummy_head.next
        
    return head

三、链表双指针

双指针（Two Pointers）：指的是在遍历元素的过程中，使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞时针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。

3.1 起点不一致的快慢指针

起点不一致的快慢指针：指的是两个指针从同一侧开始遍历链表，但是两个指针的起点不一样。 快指针 fast 比慢指针 slow 先走 n 步，直到快指针移动到链表尾端时为止。
求解步骤：

• 使用两个指针 slow、fast。slow、fast 都指向链表的头节点，即：slow = head，fast = head。
• 先将快指针向右移动 n 步。然后再同时向右移动快、慢指针。
• 等到快指针移动到链表尾部（即 fast == Node）时跳出循环体。

slow = head
fast = head

while n:
    fast = fast.next
    n -= 1
while fast:
    fast = fast.next
    slow = slow.next

3.2 步长不一致的慢指针

步长不一致的慢指针：指的是两个指针从同一侧开始遍历链表，两个指针的起点一样，但是步长不一致。例如，慢指针 slow 每次走 1 步，快指针 fast 每次走两步。直到快指针移动到链表尾端时为止。
求解步骤：

• 使用两个指针 slow、fast。slow、fast 都指向链表的头节点。
• 在循环体中将快、慢指针同时向右移动，但是快、慢指针的移动步长不一致。比如将慢指针每次移动 1 步，即 slow = slow.next。快指针每次移动 2 步，即 fast = fast.next.next。
• 等到快指针移动到链表尾部（即 fast == Node）时跳出循环体。

fast = head
slow = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

3.3 分离双指针

分离双指针：两个指针分别属于不同的链表，两个指针分别在两个链表中移动。
求解步骤：

• 使用两个指针 left_1、left_2。left_1 指向第一个链表头节点，即：left_1 = list1，left_2 指向第二个链表头节点，即：left_2 = list2。
• 当满足一定条件时，两个指针同时右移，即 left_1 = left_1.next、left_2 = left_2.next。
• 当满足另外一定条件时，将 left_1 指针右移，即 left_1 = left_1.next。
• 当满足其他一定条件时，将 left_2 指针右移，即 left_2 = left_2.next。
• 当其中一个链表遍历完时或者满足其他特殊条件时跳出循环体。

left_1 = list1
left_2 = list2

while left_1 and left_2:
    if 一定条件 1:
        left_1 = left_1.next
        left_2 = left_2.next
    elif 一定条件 2:
        left_1 = left_1.next
    elif 一定条件 3:
        left_2 = left_2.next

四、总结

本章节主要学习了链表、排序和双指针的基础知识，以及他们的求解方法，代码实现等等。