leetcode链表的总结

1:

找到中间节点：

快慢指针的运用

while(head->next!=nullptr && head->next->next!=nullptr){
	fast = fast->next->next;
	slow = slow->next;
}

最后slow就是中间节点
2:
**

两个有序链表的排序问题:

**
定义一个结构体dummy,dummy.next指向头指针

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr) return l2;
        if(l2==nullptr) return l1;
        ListNode dummy(-1);
        ListNode* tail = &dummy;
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val<l2->val){
                tail->next = l1;
                l1 = l1->next;
            }
            else{
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1==nullptr?l2:l1;
        return dummy.next;
    }
};

3:
**

链表的排序:

**
单向链表最好用归并排序，双向链表用快速排序

用了递归，所以仍然用了o(logn)的空间复杂度,因为递归用了系统栈，递归深度为完全二叉树的深度o(logn),执行了n次，所以时间复杂度为o(nlogn)
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head==nullptr || head->next==nullptr) return head;
        ListNode* slow = head,*fast = head;
        while(fast->next!=nullptr && fast->next->next!=nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = slow;
        slow = slow->next;
        fast->next = nullptr;
        ListNode* l1 = sortList(head);   //归并排序的思维，分割成小段
        ListNode* l2 = sortList(slow);
        return mergeTwoLists(l1,l2);
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr) return l2;
        if(l2==nullptr) return l1;
        ListNode dummy(-1);
        ListNode* tail = &dummy;
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val<l2->val){
                tail->next = l1;
                l1 = l1->next;
            }
            else{
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1==nullptr?l2:l1;
        return dummy.next;
    }
};

非递归，运用了递归排序的从下往上的排序方法，此时的空间复杂度为o(1)

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head==nullptr) return head;
        ListNode* cur = head;
        int len = 0;
        while(cur){
            len++;
            cur = cur->next;
        }
        ListNode dummy(-1);
        dummy.next = head;
        ListNode* left,*right,*tail;
        for(int step=1;step<len;step<<=1){
            cur = dummy.next;
            tail = &dummy;
            while(cur){
                left = cur;
                right = split(left,step);
                cur = split(right,step);
                tail = merge(left,right,tail);
            }
        }
        return dummy.next;
    }
    ListNode* split(ListNode* head,int n){
        for(int i=1;i<n && head!=nullptr;i++) head = head->next;
        if(head==nullptr) return head;
        ListNode* second = head->next;
        head->next = nullptr; //使得排序的部分是2的次方
        return second;
    }
    ListNode* merge(ListNode* l1,ListNode* l2,ListNode* head){
        ListNode* cur = head;
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val<=l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1!=nullptr?l1:l2;
        while(cur->next) cur = cur->next;
        return cur;
    }
};