这种用指针表示的数据结构一般在leetcode上才会刷到，板子简单，浅浅总结一下。

但是链表操作还是有一点思维在里面

链表操作

单链表

单链表的结构体定义：如果在本地IDE上一定要会写

struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
}; 

链表排序

单链表堆排序

非常好写，直接利用优先队列（小根堆），把所有的ListNode全部入队，然后一个一个弹出

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

struct cmp {
    bool operator ()(ListNode* a, ListNode* b) const {
        return a->val > b->val;
    }
};
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        ListNode* p = head;
        while (p != nullptr) {
            pq.push(p);
            p = p->next;
        }
        ListNode* dummyHead = new ListNode();
        p = dummyHead;
        while (!pq.empty()) {
            p->next = pq.top(); pq.pop();
            p = p->next;
        }
        p->next = nullptr; // 重定向
        return dummyHead->next;
    }
};

单链表快速排序

也还行，与数组的快排很类似

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        quickSort(head, NULL);
        return head;
    }
    
    void quickSort(ListNode* head, ListNode* tail) {
        if (head != tail) {
            // 定义哨兵x，取头指针指向的元素
            int x = head->val;
            ListNode* p = head; ListNode* q = p->next;
            while (q != tail) {
                if (q->val < x) {
                    p = p->next;
                    swap(p->val, q->val);
                }
                q = q->next;
            }
            if (p != head) {
                swap(head->val, p->val);
            }
            
            quickSort(head, p);
            quickSort(p->next, tail);
        }
    }
};

• 时间复杂度$O(n\log n)$
• 空间复杂度$O(\log n)$

单链表归并排序

这个巨抽象

反转链表

双向链表