链表排序最优算法_链表算法题

全栈程序员站长

发布于 2022-11-07 17:10:48

1.5K0

链表排序算法总结

概述

问题描述：给定一个链表，请将这个链表升序排列。

节点定义：

struct ListNode { 
   
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) { 
   }
};

1 链表插入排序

题目描述：Leetcode 0147 链表进行插入排序

分析

因为头结点可能会改变，因此需要设置一个虚拟头结点dummy。
我们从前向后遍历整个链表，假设当前考察节点为p，我们需要从dummy开始遍历，找到第一个大于p->val的前一个节点cur，然后将p插入到cur后面。

代码

class Solution { 

public:
ListNode* insertionSortList(ListNode* head) { 

auto dummy = new ListNode(-1);
for (auto p = head; p; ) { 

auto cur = dummy, next = p->next;  // next是下一个需要考察的节点
while (cur->next && cur->next->val <= p->val) cur = cur->next;
p->next = cur->next;
cur->next = p;
p = next;
}
return dummy->next;
}
};

时空复杂度分析

时间复杂度： O ( n 2 ) O(n^2) O(n2)，n为链表长度。
空间复杂度： O ( 1 ) O(1) O(1)。

2 链表归并排序

题目描述：Leetcode 0148 排序链表

分析

因为要求时间O(1)，因此就不能使用递归的写法，这一题可以使用归并排序的迭代写法（自底向上）。
这一题十分类似于Leetcode 0023 合并K个有序链表，我们可以使用LC23的思路求解。代码中的变量如下图所示：

上面的做法用C++演示。
用Java演示一下递归（自顶向下）的写法，但是空间复杂度不是 O ( 1 ) O(1) O(1)的。关键在于找到链表的中点，与Leetcode 0109 将有序链表转换二叉搜索树类似，这两题都需要找到中点，不同于LC109，LC109的终止条件是f != null && f->next != null，这里使用的终止条件是f.next != null && f->next->next != null，两者的区别为：

之后从s后截成两段，进行递归求解即可。
合并两个有序链表可以使用Leetcode 0021 合并两个有序链表的方法。

代码

class Solution { 

public:
ListNode* sortList(ListNode* head) { 

int n = 0;
for (auto p = head; p; p = p->next) n++;  // 求出节点数目
for (int len = 1; len < n; len += len) { 
  // 枚举合并长度
// 下面循环一次代表向上递推一层
auto dummy = new ListNode(-1), cur = dummy;  // 因为头结点可能变，因此需要虚拟头结点
for (int j = 1; j <= n; j += 2 * len) { 
  // 枚举待合并链表的起点, j不会再下面用到
auto p = head, q = head;
for (int i = 0; i < len && q; i++) q = q->next;
auto o = q;  // o为下次合并的起点
for (int i = 0; i < len && o; i++) o = o->next;
// 归并p、q开头的链表
int l = 0, r = 0;
while (l < len && r < len && p && q)    
if (p->val <= q->val) cur = cur->next = p, p = p->next, l++;
else cur = cur->next = q, q = q->next, r++;
while (l < len && p) cur = cur->next = p, p = p->next, l++;
while (r < len && q) cur = cur->next = q, q = q->next, r++;
head = o;  // 进行后面两段链表的合并
}
cur->next = NULL;
head = dummy->next;
}
return head;
}
};

Java

class Solution { 

public ListNode merge(ListNode l1, ListNode l2) { 

if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) { 

l1.next = merge(l1.next, l2);
return l1;
} else { 

l2.next = merge(l1, l2.next);
return l2;
}
}
public ListNode sortList(ListNode head) { 

if (head == null || head.next == null) return head;
// 快慢指针，寻找中间点
ListNode s = head, f = head;
while (f.next != null && f.next.next != null) { 

s = s.next; f = f.next.next;
}
ListNode newHead = s.next;
s.next = null;  // 断开链表，分成前后两部分
ListNode left = sortList(head), right = sortList(newHead);
return merge(left, right);  // 返回合并后的链表头指针
}
}

时空复杂度分析

时间复杂度： O ( n × l o g ( n ) ) O(n \times log(n)) O(n×log(n))，n为链表长度。
空间复杂度：C++： O ( 1 ) O(1) O(1)。Java： O ( l o g ( n ) ) O(log(n)) O(log(n))。

3 链表快速排序

题目描述：AcWing 1451. 单链表快速排序

分析

使用三个虚拟头指针left, mid, right，记录每次partition的结果，这里取头结点val的值作为分界线。
递归的过程中，我们每次都要遍历整个链表，对节点值小于val的节点接到left中，节点值等于val的节点接到mid中，节点值大于val的节点接到right中，之后还要将三个链表的尾结点置为空。
接着递归处理left、right，递归结束后将三段拼接起来即可。

代码

class Solution { 

public:
ListNode* quickSortList(ListNode* head) { 

if (!head || !head->next) return head;
auto left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1);
auto ltail = left, mtail = mid, rtail = right;
int val = head->val;
for (auto p = head; p; p = p->next) { 

if (p->val < val) ltail = ltail->next = p;
else if (p->val == val) mtail = mtail->next = p;
else rtail = rtail->next = p;
}
ltail->next = mtail->next = rtail->next = NULL;
left->next = quickSortList(left->next);
right->next = quickSortList(right->next);
// 拼接三个链表
get_tail(left)->next = mid->next;
get_tail(mid)->next = right->next;
auto p = left->next;
delete left;
delete mid;
delete right;
return p;
}
// 获取链表的尾节点
ListNode* get_tail(ListNode* head) { 

while (head->next) head = head->next;
return head;
}
};