程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Sort List

LeetCode Sort List

編輯:C++入門知識

在 O(nlogn)的時間內對一個鏈表進行排序。。明顯是要用歸並或者快排

第一次知道說原來歸並也可以用鏈表來寫,被刷了下三觀。。。。。用快慢指針的方法找分界點。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
	ListNode *getMid(ListNode *head)
	{
		ListNode *slow=head;
		ListNode *fast=head;
		while(fast->next!=NULL&&fast->next->next!=NULL)
		{
			slow=slow->next;
			fast=fast->next;
			fast=fast->next;
		}
		return slow;
	}
    ListNode *sortList(ListNode *head) 
    {
    	if(head==NULL||head->next==NULL)
    	{
    		return head;
    	}
    	ListNode *mid=getMid(head);
    	ListNode *next=mid->next;
    	mid->next=NULL;
    	return mergeList(sortList(head),sortList(next));
    }
    ListNode *mergeList(ListNode *a,ListNode *b)
    {
    	ListNode *tmphead=new ListNode(-1);
    	ListNode *cur=tmphead;
    	while(a&&b)
    	{
    		if(a->val<=b->val)
    		{
    			cur->next=a;
    			a=a->next;
    		}
    		else
    		{
    			cur->next=b;
    			b=b->next;
    		}
    		cur=cur->next;
    	}
    	cur->next=NULL;
    	cur->next= a==NULL?b:a;
    	cur=tmphead->next;
    	delete tmphead;
    	return cur;
    }
};


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved