leetcode 148. Sort List 链表归并排序

心已赠人 2022-06-08 06:24 197阅读 0赞

Sort a linked list in O(n log n) time using constant space complexity.

本题就是考察的是链表的归并排序。

代码如下：

/*class ListNode 
    {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
    }*/
    
    public class Solution
    {
        public ListNode sortList(ListNode head)
        {
            return mergeSort(head);
        }
    
        ListNode mergeSort(ListNode head) 
        {
            if(head==null || head.next==null)
                return head;
            else
            {
                ListNode head1=head;
                ListNode head2=getMidListNode(head);
    
                ListNode nextHead=head2.next;
                head2.next=null;
    
                ListNode tmp1=mergeSort(head1);
                ListNode tmp2=mergeSort(nextHead);
                return merge(tmp1,tmp2);
            }
        }
    
        ListNode merge(ListNode head1, ListNode head2)
        {
            ListNode fin=new ListNode(-1);
            ListNode cur=fin;
    
            while(head1!=null && head2!=null)
            {
                if(head1.val <= head2.val)
                {
                    //这个实在链表结尾添加结点
                    cur.next=head1;
                    head1=head1.next;
                    cur=cur.next;
                    cur.next=null;
                }else
                {
                    cur.next=head2;
                    head2=head2.next;
                    cur=cur.next;
                    cur.next=null;
                }
    
            }
            if(head1!=null)
                cur.next=head1;
            if(head2!=null)
                cur.next=head2;
    
            return fin.next;
        }
    
        ListNode getMidListNode(ListNode head) 
        {
            ListNode fast=head,slow=head;
            while(slow!=null && fast!=null && fast.next!=null && fast.next.next!=null)
            {
                slow=slow.next;
                fast=fast.next.next;
            }
            return slow;
        }
    }

下面是C++的做法，就是一个简单的归并排序的实现

代码如下：

#include <iostream>
    #include <stack>
    #include <queue>
    
    using namespace std;
    
    /*
    struct ListNode
    {
         int val;
         ListNode *next;
         ListNode(int x) : val(x), next(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        ListNode* sortList(ListNode* head) 
        {
            return mergeSort(head);
        }
    
        ListNode* mergeSort(ListNode* head)
        {
            if (head == NULL || head->next == NULL)
                return head;
            else
            {
                ListNode* h1 = head;
                ListNode* tmp = getMid(head);
                ListNode* h2 = tmp->next;
                tmp->next = NULL;
    
                h1 = mergeSort(h1);
                h2 = mergeSort(h2);
                return merge(h1, h2);
            }
        }
    
        ListNode* merge(ListNode* h1, ListNode* h2)
        {
            ListNode* fin = new ListNode(-1);
            ListNode* i = fin;
            while (h1 != NULL && h2 != NULL)
            {
                if (h1->val <= h2->val)
                {
                    i->next = h1;
                    h1 = h1->next;
                    i = i->next;
                }
                else
                {
                    i->next = h2;
                    h2 = h2->next;
                    i = i->next;
                }
            }
            if (h1 != NULL)
                i->next = h1;
            if (h2 != NULL)
                i->next = h2;
            return fin->next;
        }
    
        ListNode* getMid(ListNode* head)
        {
            ListNode* fast = head;
            ListNode* slow = head;
            while (fast != NULL && fast->next != NULL && fast->next->next != NULL)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }
    };