# leetcode148--排序链表

```输入: 4->2->1->3

```

```输入: -1->5->3->4->0

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *merge(ListNode* l1, ListNode* l2)
{
if (l1 == nullptr){
return l2;
}

if (l2 == nullptr){
return l1;
}

ListNode* root = new ListNode('#');
ListNode* p = root;

while (l1 != nullptr && l2 != nullptr)
{
if (l1->val > l2->val){
p->next = l2;
l2 = l2->next;
}
else{
p->next = l1;
l1 = l1->next;
}

p = p->next;
}

if (l1 != nullptr){
p->next = l1;
}

if (l2 != nullptr){
p->next = l2;
}

return root->next;

}

{
}

//fast->next->next != nullptr &&fast->next != nullptr则会访问到未知内存
while (fast->next != nullptr && fast->next->next != nullptr)
{
fast = fast->next->next;
slow = slow->next;
}

fast = slow;
slow = slow->next;
fast->next = nullptr;

slow = sortList(slow);

return merge(fast, slow);
}
};

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *merge(ListNode* l1, ListNode* l2)
{
if (l1 == nullptr){
return l2;
}

if (l2 == nullptr){
return l1;
}

ListNode* root = new ListNode('#');
ListNode* p = root;

while (l1 != nullptr && l2 != nullptr)
{
if (l1->val > l2->val){
p->next = l2;
l2 = l2->next;
}
else{
p->next = l1;
l1 = l1->next;
}

p = p->next;
}

if (l1 != nullptr){
p->next = l1;
}

if (l2 != nullptr){
p->next = l2;
}

return root->next;

}

{
}

//fast->next->next != nullptr &&fast->next != nullptr则会访问到未知内存
while (fast != nullptr && fast->next != nullptr)
{
p = slow;
fast = fast->next->next;
slow = slow->next;
}

p->next = nullptr;  //此处p是一个单一的节点