[leetcode]sort list-白红宇

[leetcode]sort list

阅读量：5142 次

发布时间：2019-06-13

本文共 1583 字，大约阅读时间需要 5 分钟。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };* Sort a linked list in O(n log n) time using constant space complexity.*/#include
     
      #include
      
       #include
       
        #include
        using namespace std;struct ListNode {	int val;	ListNode *next;	ListNode(int x) : val(x), next(NULL) {}};class Solution {public:	ListNode *sortList(ListNode *head) {		if (head == NULL || head->next == NULL)return head;		map
         
          > mp;		ListNode* pnode = head;		while (pnode)		{			mp[pnode->val].push_back(pnode);			pnode = pnode->next;		}		map
          
           >::iterator it = mp.begin(); head = NULL; ListNode* cur = NULL; for (; it != mp.end(); it++) { vector
           
             vec = (*it).second; for (int i = 0; i < vec.size(); i++) { if (head == NULL){ head = vec[i]; cur = vec[i]; } else{ cur->next = vec[i]; cur = cur->next; } } } cur->next = NULL; return head; }};int main(){ fstream fin("test.txt"); struct ListNode* head(0); int val = 0; //string s1 = "asdf"; //string s2(s1); //if (&s1 == &s2){ // int a = 1; //} while (fin >> val){ if (NULL == head){ head = new ListNode(val); } else { ListNode *temp = head; while (temp->next != NULL) temp = temp->next; temp->next = new ListNode(val); } } Solution solution; ListNode *new_head = solution.sortList(head); return 0;}