1 前言

• 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
• 编写代码需要对单链表有一定的了解，可以参考这里：Python实现单链表的基础功能。
• 在对单链表进行排序的代码中运用了归并排序，可以参考这里：Python实现顺序表的归并排序。

2 创建单链表

为了方便起见，直接在没有头结点的单链表上进行操作，代码如下：

# 创建结点
class Node:
    def __init__(self,element):
        self.element = element
        self.next = None
复制代码

为了后续方便创建单链表，提前准备一些必要的功能函数：

# 根据输入的列表创建链表
def single_link(list):
    for count,value in enumerate(list):
        if count == 0:                     # 首元素的插入
            head = Node(value)
            cur = head
        else:                              # 后续元素的插入
            cur.next = Node(value)
            cur = cur.next
    return head

# 以列表的形式查看链表
def traverse(node):              
        list = []                      
        while node != None:               # 遍历所有节点      
            list.append(node.element)     # 结点元素填入列表
            node = node.next             
        return list

# 计算链表长度
def length(node):
    cur = node              
    len = 0                 # 计数
    while cur != None:      # 遍历所有节点
        len += 1            # 计数
        cur = cur.next      # cur指向下一个节点
    return len   
复制代码

测试一下功能~

# 创建链表
a = single_link([99,1,34,2,6,1,35,657,5,3,8,7])

# 查看链表长度
length(a)
> 12

# 查看链表（以列表形式呈现）
traverse(a) 
> [99, 1, 34, 2, 6, 1, 35, 657, 5, 3, 8, 7]
复制代码

3 单链表反转

3.1 递归反转

以一个3结点的链表为例来梳理思路：

• 在递的过程中：

递的过程较为简单，每次都用next指针指向下一个元素，直至仅有一个结点为止（递归退出条件）

• 在归的过程中：

1. 先看过程1，由于只有一个结点，无需任何操作。
2. 再看过程2，要完成链表反转，首先需要将头结点node2.next.next指向node2，这样一来node3就成功指向了node2；之后再将node2.next指向null，就完成了链表的反转。
3. 过程3的思路与过程2思路一致，只要在过程2的结果上来反转node1即可。

• 总结一下：在归的过程中，实际上每层都反转了一个node的方向，每层的操作都一致，所以当递归完成时，整个链表的方向得以反转。

理清思路之后，代码实现就变得比较容易了：

# 链表反转(递归)
def reverse_recurse(node):
    if node == None or node.next == None:      # 递归退出条件
        return node
    res = reverse_recurse(node.next)
    node.next.next = node                      # 反转该节点指向
    node.next = None                           # 将该结点指向null
    return res
复制代码

测试一下~

# 反转链表（递归）
a = single_link([99,1,34,2,6,1,35,657,5,3,8,7])
b = reverse_recurse(a)
traverse(b) 
> [7, 8, 3, 5, 657, 35, 1, 6, 2, 34, 1, 99]
复制代码

3.2 迭代反转

同样以一个3结点的链表为例来梳理思路：

• 迭代过程比较容易理解，需要设置三个变量，不断依次向前移动，每次反转cur结点的指针，这边需要注意的是forward结点是必要的，是为了在链表断开后，cur能顺利地移动到下一个结点。

实现代码如下：

# 链表反转(迭代)
def reverse_iterate(node):
    pre = None
    cur = node
    while cur != None:                         # 遍历链表
        forward = cur.next                     # 储存cur的指针
        cur.next = pre                         # cur指向pre
        pre = cur                              # pre移动到cur的位置
        cur = forward                          # cur移动到下个位置
    return pre
复制代码

测试一下~

# 反转链表（迭代）
a = single_link([99,1,34,2,6,1,35,657,5,3,8,7])
b = reverse_iterate(a)
traverse(b) 
> [7, 8, 3, 5, 657, 35, 1, 6, 2, 34, 1, 99]
复制代码

4 单链表归并排序

1. 根据归并排序的递归思路，需要先通过递的过程将链表二分至单节点，然后通过归的过程逐级排序，如果不了解归并排序的话，可以参考这里：Python实现顺序表的归并排序。
2. 与顺序表的归并操作有所不同，单链表没法方便的索引到中间结点，只能通过遍历的方式，比较麻烦。

以一个5结点的单链表为例：

• 在递的过程中：

递的过程比较简单，就是将单链表逐层二分。二分时只要将前半部分的链表的尾结点指向null，就可以完成分割。

• 在归的过程中：

归的过程则是类似于顺序表归并排序的方式，创建一个新链表，将左右两边的结点元素依次比大小，小的填入新链表，链表后移一位，再次比大小，以此类推。

实现代码如下：

def merge_sort(node):
    if length(node) <= 1:           # 递归退出条件
        return node
    split = length(node)//2-1       # 二分点（因为python索引从0开始，所以-1）
    cur1 = node
    cur2 = node.next
    for _ in range(split):          # 移动到二分点处
        cur1 = cur1.next
        cur2 = cur2.next
    cur1.next = None                # 将前半部分的尾结点指向null
    left = merge_sort(node)
    right = merge_sort(cur2)
    return sort(left, right)        


def sort(left, right):
    cur = Node(0)                             # 新建链表，数值随意，后面会去掉这个结点
    head = cur
    while left != None and right != None:     # 依次比大小
        if left.element < right.element:
            cur.next = Node(left.element)
            cur = cur.next
            left = left.next                  
        else:
            cur.next = Node(right.element)
            cur = cur.next
            right = right.next
    if left != None:                           # 直接接上剩余的结点
        cur.next = left
    if right != None:
        cur.next = right
    res = head.next                           
    head.next = None                           # 去除多余的头结点
    return res
复制代码

测试一下~

# 链表归并排序
a = single_link([99,1,34,2,6,1,35,657,5,3,8,7])
b = merge_sort(a)
traverse(b)  
> [1, 1, 2, 3, 5, 6, 7, 8, 34, 35, 99, 657]
复制代码