1. 链表简介
链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。
链表中每个数据的存储都由以下两部分组成：
- 数据元素本身，其所在的区域称为数据域；
- 指向直接后继元素的指针，所在的区域称为指针域；
2. 链表的基本操作
数据结构的操作一般涉及到增、删、改、查 4 种情况，链表的操作也基本上是这 4 种情况。
2.1链表的创建（初始化）
同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：
- 插入到链表的头部（头节点之后），作为首元节点；
- 插入到链表中间的某个位置；
- 插入到链表的最末端，作为链表中最后一个数据元素；
# 根据 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
# 头部插入元素
def insertFront(self, val):
node = ListNode(val)
node.next = self.head
self.head = node
# 中间插入元素
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
# 尾部插入元素
def insertRear(self, val):
node = ListNode(val)
cur = self.head
while cur.next:
cur = cur.next
cur.next = node
2.2 删除元素
从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除，但作为一名合格的程序员，要对存储空间负责，对不再利用的存储空间要及时释放。因此，从链表中删除数据元素需要进行以下 2 步操作：
- 将结点从链表中摘下来;
- 手动释放掉结点，回收被结点占用的存储空间;
# 链表头部删除元素
def removeFront(self):
if self.head:
self.head = self.head.next
# 链表中间删除元素
def removeInside(self, index):
count = 0
cur = self.head
while cur.next and count < index - 1:
count += 1
cur = cur.next
if not cur:
return 'Error'
del_node = cur.next
cur.next = del_node.next
# 链表尾部删除元素
def removeRear(self):
if not self.head.next:
return 'Error'
cur = self.head
while cur.next.next:
cur = cur.next
cur.next = None
2.3 改变元素
改变链表中的元素，只需通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可。
# 改变元素
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
2.4 查找元素
在链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL（比对失败的标志）。
# 查找元素
def find(self, val):
cur = self.head
while cur:
if val == cur.val:
return cur
cur = cur.next
return None
3.链表排序
链表的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。
3.1链表冒泡排序
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
3.2 链表选择排序
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
3.3. 链表插入排序
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
3.4 链表归并排序
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))
3.5. 链表快速排序
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
3.6链表计数排序
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.next
等有空再来补充。。。