148链表排序

148. 排序链表

下面是题目

下面是题目给出的代码模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        
    }
};

因为我自己不会直接在链表上操作，所以我用了multiset存储

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        multiset<int>st;
        ListNode*cur = head;
        while(cur)
        {
            //首先，把所有的链表信息都存放在multiset中，因为multiset会自己排序
            st.insert(cur->val);
            cur = cur->next;
        }
         ListNode *dummy = new ListNode(0);
         ListNode *head2 = dummy;
        
        for(set<int>::iterator it = st.begin();it!=st.end();it++)
        {
            //第二步，就是每次从set中取出一个数据，建立新的节点，然后尾插法
            ListNode *newNode = new ListNode(*it);
            dummy->next= newNode;
            dummy = dummy->next;
        }
        return head2->next;
    }
};