链表的归并排序
程序员文章站
2022-05-10 17:19:14
...
链表的归并 主要有2种方法。
- 自顶向下的递归法
- 自底向上的非递归法
在讨论具体的归并排序前,必须清楚以下几个问题!
-
如何找到链表中点? ----------------------------->快慢指针法.
public Link find_Mid(Link head)
{
Link fast = head;
Link slow = head;
while(fast.next!=null && fast.next.next != null){ // 只要快的没到终点
fast = fast.next.next; // 快的走两步
slow = slow.next; // 慢的走一步
}
return slow; // 慢指针所指 即为链表中点
}
-
如何归并2个有序链表? ----------------------------> 穿针引线法 / 递归法
-
穿针引线法
public LinkNode merge(LinkNode a,LinkNode b)
{
LinkNode temp = new LinkNode(0); // 这就是针
LinkNode oldtemp = temp;
while(a != null && b!= null){
if(a.val <= b.val){
temp.next = a; // 这就是线
a = a.next;
}else{
temp.next = b;
b = b.next;
}
temp = temp.next;
}
if(a == null)
temp.next = b;
if(b == null)
temp.next = a;
return oldtemp.next;
}
2.递归法
public LinkNode merge(LinkNode a,LinkNode b)
{
if(a == null) return b; // 递归终止条件--> 任一链表归并完毕
if(b == null) return a;
if(a.val <= b.val){ // 如果 a 节点比 b 节点 小
a.next = merge(a.next,b); // 那么a的下一个节点继续和原来的b节点比较
return a; // 返回 值小的节点。
}else{
b.next = merge(b.next,a);
return b;
}
}
-
如何归并 k 个 有序链表? -----------------------------------> 空指针法.
public LinkNode merge_k(LinkNode a,LinkNode b,LinkNode c) // 这里用3个有序链表为例
{
LinkNode[] count = new LinkNode[3]; // 创建一个结构数组来保存节点
count[0] = a;
count[1] = b;
count[2] = c;
LinkNode res = null; // 设置一个空指针
for(int i = 0; i <3; k++){ // 开始遍历数组
if(count[i] != null)
res = merge(res,count[i]); // 这里用到 归并2个有序链表的操作
}
return res;
}
搞清楚这几个操作后,开始进入归并排序!
先看 自顶向下的递归法:
思路: 给一个链表,从中间断开,如此循环,直到断成单个节点,然后归并。
public Link sort(Link head)
{
if(head == null || head.next == null) // 递归终止条件--> 空节点或单个节点时,递归结束
return head;
Link mid = find_Mid(head); // 找到中点
Link second = mid.next; // 设置第二个递归节点。即另一条链表的起始位置
mid.next = null; // 断开链表
Link left = sort(head); // 开始递归
Link right = sort(second);
return merge(left,right); // 返回合并后的节点
}
接着来看 自底向上的 非递归法:
思路: 给一个链表,从起点开始,单拿一个节点放入数组,只要数组位置已经有节点占用,则归并这两个节点,同时向后移动一个位置。重复这个过程直到拿完链表所有节点。
public Link sort(Link head)
{
Link[] counter = new Link[64]; // 创建一个结构数组。 可归并 2^64个节点,足够了
int maxIndex = 0; // 后面归并多个链表会用到
Link cur = null; // 指向拿出的单个节点
while(head != null){ // 只要链表中还有节点
cur = head;
head = head.next;
cur.next = null; // 单拿出来
int i = 0;
while(counter[i] != null){ // 如果此位置已被占用
Link newLink = merge(cur,counter[i]); // 归并
counter[i] = null; // 把该位置清空
i++; // 向后移动一位
cur = newLink; // 归并完成后的节点 赋值给 cur,开始下一次循环
}
counter[i] = cur; // 如果该位置没有节点, 直接放入。
if(i > maxIndex)
maxIndex = i; // 保存此时的i。 即最后被占用的位置下标
}
// 当链表的节点都被拿完:
Link res = null; // 这里用到了归并 k 个 链表 的 操作
for(int i = 0; i <= maxIndex; i++){
if(counter[i] != null )
res = merge(counter[i],res);
}
return res;
}
上一篇: 陈家最后的骨气,陈叔慎拼死报国!
下一篇: 黄麻起义爆发的原因是什么 黄麻起义简介