链表

2.反转链表

头插法形成一个环形的指向

    ListNode* ReverseList(ListNode* pHead) {
        ListNode* dummy = nullptr;
        auto cur = pHead;
        auto curNext = cur;
        while (cur) {
            curNext = cur->next;
            cur->next = dummy;
            dummy = cur;
            cur = curNext;
        }
        return dummy;
    }

3.合并两个排序的链表

递归

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1) return pHead2;
        if (!pHead2) return pHead1;
        
        if (pHead1-> val < pHead2->val) {
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        } else {
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }

迭代

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1) return pHead2;
        if (!pHead2) return pHead1;
        ListNode* dummy = new ListNode(-1);
        auto pre = dummy;
        while (pHead1 and pHead2) {
            if (pHead1->val <= pHead2->val) {
                pre->next = pHead1;
                pHead1 = pHead1->next;
            } else {
                pre->next = pHead2;
                pHead2 = pHead2->next;
            }
            pre = pre->next;
        }
        if (pHead1) pre->next = pHead1;
        if (pHead2) pre->next = pHead2;
         
        return dummy->next;
    }

4.两个链表的第一个公共节点

链表走完就走向另一个链表的入口，相遇时刚好走过相等的路程。

    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1 or !pHead2) return nullptr;
        ListNode* p1 = (ListNode*)malloc(sizeof(ListNode));
        auto p2 = new ListNode(0);
        p1 = pHead1, p2 = pHead2;
        while (p1 != p2) {
            p1 = (p1 == nullptr ? pHead2 : p1->next);
            p2 = (p2 == nullptr ? pHead1 : p2->next);
        }
        return p1;
    }

或者使用哈希表 任取一条链表遍历并将节点存储到哈希表中，再遍历另外一条链表的节点是否在哈希表中。

5.链表中环的入口节点

哈希表 空间复杂度稍高。

    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        unordered_set<ListNode*> uset;
        while (pHead != nullptr) {
            if (uset.count(pHead)) {
                return pHead;
            }
            uset.emplace(pHead);
            pHead = pHead->next;
        }
         
        return nullptr;
    }

快慢指针 快指针一次走两步，慢指针一次走一步，第一次相遇时再将快指针放到头结点处，然后快慢指针以相同的速度向前，相遇处就是环形链表的入口。（画图写出数学关系更容易理解）

    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        auto fast = pHead;
        auto slow = pHead;
        do {
            if (!fast->next->next or !fast->next) {
                return nullptr;
            }
            fast = fast->next->next;
            slow = slow->next;
        }while (fast != slow);
        
        fast = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }

6.链表中最后k个结点

快慢指针 快指针先向前走k步，慢指针再往前走直到快指针走到末尾。

    ListNode* FindKthToTail(ListNode* pHead, int k) {
        if (!pHead) return nullptr;
        auto pre = pHead, res = pHead;
        while (k--) {
            if (!pre) return nullptr;
            pre = pre->next;
        }
        while (pre) {
            pre = pre->next;
            res = res->next;
        }
        return res;
    }

7.复杂链表的复制

哈希表 第一次遍历创建并存储对应的节点，第二遍遍历对每个哈希表中的节点进行赋值。

    RandomListNode* Clone(RandomListNode* pHead) {
        if (!pHead) return nullptr;
        unordered_map<RandomListNode*, RandomListNode*> umap;
        for (auto iter = pHead; iter; iter = iter->next) {
        //key：当前节点，value：当前节点的值，但是next和random都是空节点
            umap[iter] = new RandomListNode(iter->label);
        }
        for (auto iter = pHead; iter; iter = iter->next) {
        //第二遍遍历需要对对应的值进行遍历，使用上一次遍历保存key的值
            umap[iter]->next = umap[iter->next];
            umap[iter]->random = umap[iter->random];
        }
        return umap[pHead];
    }

    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
        //创建单个节点并对其进行赋值包括val next 和random
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = node->next;
            nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
        }
        Node* headNew = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* nodeNew = node->next;
            node->next = node->next->next;
            nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
        }
        return headNew;
    }

8.删除链表中的重复节点

使用一个pre节点寻找与当前节点值不同的数。

    ListNode* deleteDuplication(ListNode* pHead) {
        if (!pHead or !pHead->next) return pHead;
        auto dummy = new ListNode(-1);
        dummy->next = pHead;
        auto cur = dummy;
        while (cur->next) {
            ListNode* pre = cur->next;
            while (pre and cur->next->val == pre->val) {
                pre = pre->next;
            }
            //如果只向前走了一步那就走一步，否则就跳到那个位置
            if (cur->next->next == pre) cur = cur->next;
            else cur->next = pre;
        }
        return dummy->next;
    }

9.删除链表节点

这个题的节点数值是唯一的。

    ListNode* deleteNode(ListNode* head, int val) {
        if (!head) return nullptr;
        if (head->val == val) {
            return head->next;
        }
        auto dummy = new ListNode(-1);
        dummy->next = head;
        //pre节点错后cur节点一个身位
        auto pre = dummy, cur = head;
        while (head) {
            if (cur->val == val) {
                pre->next = cur->next;
                break;
            } else {
                cur = cur->next;
                pre = pre->next;
            }
        }
        
        return dummy->next;
    }

10.链表相加Ⅱ

给出倒序链表，要求相加之后正序输出。

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        if (!head1) return head2;
        if (!head2) return head1;
        stack<int> stk1, stk2;
        for (auto p = head1; p; p = p->next) {
            stk1.push(p->val);
        }
        for (auto p = head2; p; p = p->next) {
            stk2.push(p->val);
        }
        int t = 0;
        ListNode* head = nullptr;
        while (stk1.size() or stk2.size()) {
            if (stk1.size()) {
                t += stk1.top();
                stk1.pop();
            }
            if (stk2.size()) {
                t += stk2.top();
                stk2.pop();
            }
            auto node = new ListNode(t % 10);
            t /= 10;
            node->next = head;
            head = node;
        }
        if (t) {
            auto node = new ListNode(t);
            node->next = head;
            head = node;
        }
        return head;
    }

11.链表内指定区间反转

设置区间

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n) return head;
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto a = dummy, d = dummy;
        for (int i = 0; i < m - 1; ++i) a = a->next;
        for (int i = 0; i < n; ++i) d = d->next;
         
        auto b = a->next, c = d->next;
        for (auto p = b, q = b->next; q != c;) {
            auto qNext = q->next;
            q->next = p;
            p = q;
            q = qNext;
        }
        b->next = c;
        a->next = d;
        return dummy->next;
    }

    ListNode* reverseBetween(ListNode* head, int left, int right) {
        auto dummy = new ListNode(-1, head);
        auto pre = dummy;
        for (int i = 1; i < left; ++i) {
            pre = pre->next;
        }
        //定位到当前要反转的链表头节点
        head = pre->next;
        ListNode* curNext = nullptr;
        for (int i = left; i < right; ++i) {
            curNext = head->next;
            head->next = curNext->next;
            curNext->next = pre->next;
            pre->next = curNext;
        }
        return dummy->next;
    }

牛客排名第一的C++题解，学习一下源地址

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy, * cur = head;
        for (int i = 1; i < m; i++) {
            pre = pre->next;
        }
        cur = pre->next;
        for (int i = 0; i < n - m; i++) {
            ListNode* temp = cur->next;
            cur->next = cur->next->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return dummy->next;
    }

12.k个一组反转链表

class Solution {
    auto reverse(ListNode* left, ListNode* right) {
        auto node = right;              //右边节点
        while (left != right) {
            auto cur = left->next;
            left->next = node;
            node = left, left = cur;
        }
        return node;
    }
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k == 1) return head;
        auto cur = head;
        for (int i = 0; i < k; ++i) {
            if (!cur) return head;     //不足k个不需要反转
            cur = cur->next;
        }
        auto res = reverse(head, cur);      //对区间【head，cur】进行翻转
        head->next = reverseKGroup(cur, k); //下一个区间
        return res;
    }
};

13.链表的插入排序

    ListNode* insertionSortList(ListNode* head) {
        if (!head or !head->next) return head;
        auto dummy = new ListNode(-1);
        while (head) {
            //当前从哑节点开始算起
            auto pre = dummy;
            //已经是有序前向节点就一直向前走
            while (pre->next and pre->next->val < head->val) pre = pre->next;
            //保存当前已经排好的节点末尾
            auto curHead = head;
            head = head->next;
            //前向节点指向当前节点
            curHead->next = pre->next;
            pre->next = curHead;
        }
        return dummy->next;
    }

14.旋转链表

    ListNode* rotateRight(ListNode* head, int k) {
        //统计链表长度
        if (!head or !head->next) return head;
        int n = 0;
        for (auto p = head; p; p = p->next) n++;
        k %= n;
        auto fast = head, slow = head;
        while (k--) fast = fast->next;
        while (fast->next){
            fast = fast->next;
            slow = slow->next;
        }
        fast->next = head;
        head = slow->next;
        slow->next = nullptr;
        return head;
    }

15.合并k个升序链表

和第三题几乎一样

class Solution {
    ListNode* merge(ListNode* a, ListNode* b) {
        if (!a) return b;
        if (!b) return a;
        if (a->val <= b->val) {
            a->next = merge(a->next, b);
            return a;
        } else {
            b->next = merge(a, b->next);
            return b;
        }
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* head = nullptr;
        for (auto node: lists) {
            head = merge(head, node);
        }
        return head;
    }
};

LeetCode上的堆优化版本

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

暴力求解好像也没有那么慢

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        multiset<int> mset;
        for (auto &list : lists) {
            while (list) {
                mset.insert(list->val);
                list = list->next;
            }
        }
        ListNode* dummy = new ListNode(0);
        auto cur = dummy;
        for (int num : mset) {
            auto node = new ListNode(num);
            cur->next = node;
            cur = cur->next;
        }
        return dummy->next;
    }
};

16.两两交换链表中的节点

画图较为容易理解，注意先后指向的顺序。

    ListNode* swapPairs(ListNode* head) {
        auto dummy = new ListNode(0, head);
        for (auto p = dummy; p->next && p->next->next;) {
        //a表示下一个节点，b表示下下一个节点 p
            auto a = p->next, b = p->next->next;
            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }
        return dummy->next;
    }

17.奇偶链表

链表的第1、3、5...个节点放在前面，2、4、6节点放在后面，保持相对顺序。

    ListNode* oddEvenList(ListNode* head) {
        if (!head or !head->next) {
            return head;
        }
        //当前的奇数节点头，当前的偶数节点头，odd和even用于遍历
        auto odd = head, even = head->next;
        auto oddHead = odd, evenHead = even;
        while (odd->next and even->next) {
            //保存odd下一个节点，每次往前走两步
            auto oddNext = odd->next->next;
            odd->next = oddNext;
            odd = oddNext;

            auto evenNext = even->next->next;
            even->next = evenNext;
            even = evenNext;
        }
        odd->next = evenHead;
        return oddHead;
    }