148. 排序链表

148. 排序链表

1.想法:

利用归并排序,达到降低时间复杂度的效果,但是怎么知道其中间节点呢?网上的思路是利用快慢指针的方式,就是

ListNode midNode = head,endNode = head;
        while(endNode!=null&&endNode.next!=null){}
            midNode = midNode.next;
            endNode = endNode.next.next;
        }

最终获得midNode就是中间节点,也就是说我们把数据分成了两半了,那么此时我们肯定要合并两个排好序的ListNode,在哪里?我们可以继续分子问题,只要节点数量!=1那么就进行划分,当等于1的时候就相当于排好序了,此时再和另一个排好序的ListNode进行合并,

        ListNode myHead = sortList(head);  
       //但是这里的myHead会一直循环下去,因为使用的是head,我们知道head后面的数据是一整条链,
      //所以我们需要进行截断链的操作,什么时候截断,在哪里截断?
       //在midNode的前一个截断,那么我们需要记录一下
        ListNode newMid = sortList(midNode);

2.代码

 public ListNode sortList(ListNode head) {
        if(head==null||head.next == null)return head;
        ListNode midNode = head,endNode = head,pre=null;
        while(endNode!=null&&endNode.next!=null){
            if(pre == null){
                pre = head;
            }else{
                pre = pre.next;
            }
            midNode = midNode.next;
            endNode = endNode.next.next;
        }
        pre.next = null;

        ListNode myHead = sortList(head);
        ListNode newMid = sortList(midNode);

        ListNode newNode = null;
        if(myHead.val<newMid.val){
            newNode = new ListNode(myHead.val);
            myHead = myHead.next;
        }else{
            newNode = new ListNode(newMid.val);
            newMid = newMid.next;
        }
        ListNode newHead = newNode;
        while(myHead!=null&&newMid!=null){
            if(myHead.val<newMid.val){
                newHead.next=new ListNode(myHead.val);
                myHead = myHead.next;
            }else{
                newHead.next=new ListNode(newMid.val);
                newMid = newMid.next;
            }
            newHead = newHead.next;
        }
        if(myHead!=null){
            newHead.next = myHead;
        }
        if(newMid!=null){
            newHead.next = newMid;
        }
        return newNode;
    }