欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

链表的归并排序

程序员文章站 2022-05-10 17:19:14
...

链表的归并 主要有2种方法。

  1. 自顶向下的递归法
  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个有序链表?  ----------------------------> 穿针引线法 / 递归法

  1. 穿针引线法

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;
	}