c++-常用数据结构-linkedList相关操作

链表的基本操作
链表逆序
链表打印
链表排序： 排序， 归并排序， 快排排序

#include 
#include 
#include 

using namespace std;

struct ListNodeIterator;

struct ListNode {
    struct ListNode *next;
    int val;

    explicit ListNode(int val) : next(nullptr), val(val) {}

    ListNodeIterator begin();

    static ListNodeIterator end();
};

#define if_null_return(node, r) 
    if (nullptr == head) { 
        return r;    
    }

#define NULLRETURN

struct ListNodeIterator {
    ListNode *node;

    explicit ListNodeIterator(ListNode *node) : node(node) {}

    int &operator*() {
        return node->val;
    }

    ListNodeIterator operator++() {
        node = node->next;
        return *this;
    }

    bool operator!=(ListNodeIterator other) const {
        return node != other.node;
    }
};

ListNodeIterator ListNode::begin() {
    return ListNodeIterator(this);
}

ListNodeIterator ListNode::end() {
    return ListNodeIterator(nullptr);
}

ListNode *makeList(const vector &data) {
    ListNode dummy(-1);
    ListNode *tail = &dummy;
    for (auto v: data) {
        auto next = new ListNode(v);
        tail->next = next;
        tail = tail->next;
    }
    return dummy.next;
}

void printList(ListNode *head) {
    if_null_return(head, NULLRETURN)
    for (auto val: *head) {
        cout << val << "t";
    }
    cout << endl;
}

ListNode *reverseList(ListNode *head) {
    ListNode *pre = nullptr;
    ListNode *cur = head;
    while (nullptr != cur) {
        ListNode *next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

ListNode *sortList(ListNode *head, function cmp = less<>{}) {
    if_null_return(head, nullptr)
    vector data;
    for (auto v: *head) {
        data.emplace_back(v);
    }
    sort(data.begin(), data.end(), std::move(cmp));
    auto it = data.begin();
    for (auto &v: *head) {
        v = *it++;
    }
    return head;
}

ListNode *_listNodePartition(ListNode *head, ListNode *tail, const function &cmp) {
    if_null_return(head, nullptr)
    ListNode *q = head;
    int pivot = head->val;
    ListNode *p = head;
    while (p != tail) {
        if (cmp(p->val, pivot)) {
            q = q->next;
            swap(q->val, p->val);
        }
        p = p->next;
    }
    swap(head->val, q->val);
    return q;
}

ListNode *quickSort(ListNode *head, ListNode *tail = nullptr, const function &cmp = less<>{}) {
    if (head == tail || head == nullptr) {
        return nullptr;
    }
    ListNode *q = _listNodePartition(head, tail, cmp);
    quickSort(head, q, cmp);
    if (q && q->next) {
        quickSort(q->next, tail, cmp);
    }
    return head;
}

ListNode *mergeSortedList(ListNode *left, ListNode *right, const function &cmp = less<>{}) {
    ListNode dummy(-1);
    ListNode *tail = &dummy;
    while (left && right) {
        if (left->val <= right->val) {
            tail->next = left;
            left = left->next;
        } else {
            tail->next = right;
            right = right->next;
        }
        tail = tail->next;
    }
    if (left) {
        tail->next = left;
    }
    if (right) {
        tail->next = right;
    }
    return dummy.next;
}

ListNode *findPreMid(ListNode *head) {
    if (!head || !head->next) {
        return nullptr;
    }
    ListNode *slow = head;
    ListNode *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

ListNode *mergeSort(ListNode *head, const function &cmp = less<>{}) {
    if (!head || !head->next) {
        return head;
    }
    // 切分为两个链表
    ListNode *preMid = findPreMid(head);
    ListNode *rightHead = preMid->next;
    // 断开链表
    preMid->next = nullptr;
    //
    ListNode *left = mergeSort(head, cmp);
    ListNode *right = mergeSort(rightHead, cmp);
    return mergeSortedList(left, right, cmp);
}

int main() {
    auto data = {2, 1, 3, 4, 5, 6};
    auto list = makeList(data);
    printList(list);

    auto reverse_list = reverseList(list);

    printList(reverse_list);

    auto sorted_list = quickSort(reverse_list, nullptr);
    printList(sorted_list);

    sorted_list = quickSort(reverse_list, nullptr, greater<>{});
    printList(sorted_list);

    sorted_list = mergeSort(reverse_list, less<>{});
    printList(sorted_list);

}