使用归并排序对链进行排序(超简单)
使用归并排序对链进行排序
首先归并排序的中心归并两个已经有序的数组。归并两个有序数组A和B,就生成了第三个有序数组C。数组C包含数组A和B的所有数据项。
先找到一个链的中间链,然后左右开始排序!
数组的中间很好找但是一个链的tm的中间链怎么找,循环一下i++得到总长 然后在找中间链???黑人问号
观察上面图你能发现什么?
b走两步a走一步,a永远是在b中间的点,有没有,哈哈,是不是很神奇
现在我们知道了如何找中间点的思路,那么开始吧
/**
*
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return head == null ? null : mergeSort(head);
}
private ListNode mergeSort(ListNode head) {
if(head.next==null)//head.next==null说明它后面没有节点了,都t喵没有节点了,当然返回咯
{
return head;
}
// slowp慢指针 fastp指针 慢指针的上一个节点
ListNode slowp=head,fastp=head,pre=null;
while(fastp!=null&&fastp.next!=null)//快指针什么时候结束,它是null的时候,和它next=null的时候
{
pre=slowp;
slowp=slowp.next;
fastp=fastp.next.next;
}
pre.next=null;//pre (中间节点的上一个节点) 的next=null,让它们之间断了联系
ListNode l= sortList(head);
ListNode r= sortList(slowp);
return merge(l,r);
}
ListNode merge(ListNode l, ListNode r) {
ListNode re=new ListNode(-1);//用来存储要返回的最小的头
ListNode temporary=re;//临时的节点
while(l!=null&&r!=null)
{
if(l.val<r.val)// l.val小于r.val
{
temporary.next=l;//当前temporary指向 re 所以re.next=l 后面的 temporary 指向l
temporary=l;//temporary 指向 l
l=l.next;//当前的l的val小与r的val说明 当前l的val小于r的全部 因为都是有序的
}else
{
//同理
temporary.next=r;
temporary=r;
r=r.next;
}
}
if(l!=null)//如果上面那个while什么时候结束在(l!=null&&r!=null)时结束 比如 节点1 和节点2比较 节点1<点2(节点二后面) re.next=节点1 temporary=节点1
{
temporary.next=l;//temporary=节点1 temporary.next=节点2
}
if(r!=null)//同理
{
temporary.next=r;
}
return re.next;
}
}
。。。。说也说不好。。画图也也不会。。。。。
敲一下理解一下逻辑就应该知道了 ok