Merge sort fast runner


  • 0
    Y
    //merge sort, merge sort
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode SortList(ListNode head) {
            if(head==null||head.next==null)
                return head;
            //get mid of the linked list
            ListNode slow = head;
            ListNode pre = new ListNode(0);
            ListNode fast = head;
            while(fast!=null&&fast.next!=null)
            {
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            pre.next=null;
            ListNode left=SortList(head);
            ListNode right=SortList(slow);
            return Merge(left,right);
        }
        public ListNode Merge(ListNode head1,ListNode head2)
        {
            if(head1==null)
                return head2;
            if(head2==null)
                return head1;
            var dumHeader=new ListNode(0);
            ListNode record = dumHeader;
            while(head1!=null&&head2!=null)
            {
                if(head1.val<head2.val)
                {
                    var temp=head1.next;
                    head1.next=null;
                    dumHeader.next=head1;
                    dumHeader=head1;
                    head1=temp;
                }
                else
                {
                    var temp=head2.next;
                    head2.next=null;
                    dumHeader.next=head2;
                    dumHeader=head2;
                    head2=temp;
                }
            }
            if(head1!=null)
            {
                dumHeader.next=head1;
            }
            if(head2!=null)
            {
                dumHeader.next=head2;
            }
            return record.next;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.