408相关算法刷题【链表篇】

前言

LeetCode 2. 两数相加（**）

题目类型

1. 链表

题目链接

https://leetcode.cn/problems/add-two-numbers/

思路

跟加法逻辑一下 保存进位carry

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* res = new ListNode(-1);
        ListNode* cur = res;

        int carry = 0;
        while(l1 || l2)
        {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = carry + n1 + n2;
            carry = sum / 10;
            cur -> next = new ListNode(sum % 10);
            cur = cur -> next;
            if (l1) l1 = l1 -> next;
            if (l2) l2 = l2 -> next;    
        }
        if (carry) cur -> next = new ListNode(carry);
        return res->next;
    }
};

LeetCode 19. 删除链表的倒数第N个节点（**）

题目类型

1. 链表的删除
2. 双指针应用

题目链接

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

思路

注意加个头结点防止只有一个元素，而要删除该元素
方法一：数学方法

1. p指向头结点
2. 让p走k - n - 1步即可到达删除结点的前驱，其中k为链表长度

方法二：双指针（时间更快）

1. 都指向头结点
2. q走n + 1步
3. p q同时走 当q到达尾部NULL时候，p指向倒数第n个数的前驱

AC代码1

方法一：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy_head = new ListNode(-1);
        dummy_head->next = head;

        int k = 0;
        auto p = dummy_head;
        while(p->next)
        {
            k ++;
            p = p->next;
        }
        auto q = dummy_head;
        for (int i = 0; i < k - n; i ++) q = q->next;
        q->next = q->next->next;
        return dummy_head->next;
    &#125;
&#125;;

AC代码2

方法二：时间更快

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy_head = new ListNode(-1);
        dummy_head->next = head;

        ListNode* p = dummy_head;
        ListNode* q = dummy_head;

        // 先让q走n + 1步 因为前面有虚拟结点
        for (int i = 0; i < n + 1; i ++) q = q->next;

        while (q)
        &#123;
            p = p->next;
            q = q->next;
        &#125;
        p->next = p->next->next;
        return dummy_head->next;
    &#125;
&#125;;

LeetCode 21. 合并两个有序链表（*）

题目类型

1. 链表
2. 升序序列的合并问题

题目链接

https://leetcode.cn/problems/merge-two-sorted-lists/

思路

1. 遍历两个链表，每次选择最小的数添加到新链表的尾部即可
2. 最后两个链表可能存在一个还有未插入序列，将该序列插入即可，这里有两种写法，一种是我自己写的不够精简，y总的写法比较精简（有时候看y总代码真是有种看艺术品感觉）

   while (l1) cur->next = l1, l1 = l1->next, cur = cur->next;
   while (l2) cur->next = l2, l2 = l2->next, cur = cur->next;

cur->next = (l1 == NULL ? l2 : l1);

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;

        while (l1 && l2)
        {
            if (l1->val < l2->val)
            &#123;
                cur->next = l1;
                l1 = l1->next;
            &#125;
            else
            &#123;
                cur->next = l2;
                l2 = l2->next;
            &#125;
            cur = cur->next;
        &#125;
        // while (l1) cur->next = l1, l1 = l1->next, cur = cur->next;
        // while (l2) cur->next = l2, l2 = l2->next, cur = cur->next;

        cur->next = (l1 == NULL ? l2 : l1);
        return dummy->next;
    &#125;
&#125;;

LeetCode 23. 合并K个排序链表（***）

题目类型

1. 链表
2. 小根堆
3. k路合并问题

题目链接

https://leetcode.cn/problems/merge-k-sorted-lists/

思路

此题和21题类似，只不过21题是2路合并，该题是k路合并，思路如下：

1. 每次取k个链表中首部最小的那个数
2. 将该数插到结果链表
3. 直到所有链表都插入完
   很容易得知该时间复杂度为$O(K*N)$

此处可以用小根堆做优化

1. 初始时将每个链表的首部放入堆中
2. 每次取堆顶，并把堆顶t 做一次pop()
3. 将链表尾部指向t，并若t->next不为空，继续将t->next放入堆中
   该时间复杂度为$O(Nlogk)$

   AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct Cmp
    {
        bool operator()(ListNode* a, ListNode* b)
        {
            return a->val > b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) &#123;
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        auto dummy = new ListNode(-1), p = dummy;
        // 将每个链表的第一个元素（也就是最小数）放入堆中
        for (auto l : lists) if (l) heap.push(l);

        while (heap.size())
        &#123;
            // 取堆顶
            auto t = heap.top();
            heap.pop();

            p->next = t;
            p = t;

            if (t->next) heap.push(t->next);
        &#125;

        return dummy->next;
    &#125;
&#125;;

LeetCode 24. 两两交换链表中的节点（**）

题目类型

1. 链表
2. 交换问题

题目链接

https://leetcode.cn/problems/swap-nodes-in-pairs/

思路

对于p->a->b，其中p为虚拟头结点
交换ab只需要

p->next = b;
a->next = b->next;
b->next = a;

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy;
        while (p->next && p->next->next)
        {
            auto a = p->next, b = a->next;

            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }
        return dummy->next;
    }
};

LeetCode 25. K 个一组翻转链表（***）

题目类型

1. 链表
2. k组翻转

题目链接

https://leetcode.cn/problems/reverse-nodes-in-k-group/

思路

此时看起来不难，实际实现的时候很容易出错，建议多刷几次

1. 每次检验是否下一组足够k个元素，不够则break 够的话继续往下执行
2. 对于 p->a->b->c->d 从a开始进行k-1次循环反转指针,而且注意在反转指针之前要把b->next存起来

   auto c = b->next, b->next = a

3. k-1次之后（也就是该组已经反转成功后） 此时将p->next->next = b，落到了下一组以b为开始的反转的前一个结点（可以看做是虚拟结点）
4. 继续以上操作

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        for (auto p = dummy;;)
        {
            // 判断是否满足k个元素
            auto q = p;
            for (int i = 0; i < k && q; i ++) q = q->next;
            if (!q) break; // 不满足直接跳出


            // 满足有k个元素
            auto a = p->next, b = a->next;
            for (int i = 0; i < k - 1; i ++) // 内部交换k - 1次
            &#123;
                auto c = b->next;
                b->next = a;
                a = b, b = c;
            &#125;
            auto t = p->next;
            p->next = a;
            t->next = b;
            p = t;
        &#125;
        return dummy->next;
    &#125;
&#125;;

LeetCode 82. 删除排序链表中的重复元素 II

题目类型

1. 删除操作

题目链接

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/

思路

这里解法一是自己写的方法

解法二是y总的，y总代码比较精简，y总的题解：https://www.acwing.com/solution/content/166/

AC代码一

// 朴素法
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return head;

        // 创建虚拟头结点
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = dummy;

        // 遍历
        while (cur->next && cur->next->next)
        {
            if (cur->next->val == cur->next->next->val)
            {
                int x = cur->next->val;
                while (cur->next && cur->next->val == x)
                {
                    cur->next = cur->next->next;
                }    
            }
            else
            {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

AC代码二

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* p = dummy;

        while (p->next)
        {
            ListNode* q = p->next->next;
            while (q && q->val == p->next->val) q = q->next;
            if (p->next->next == q) p = p->next;
            else p->next = q;
        }
        return dummy->next;
    }
};

LeetCode 83. 删除排序链表中的重复元素

题目类型

1. 删除

题目链接

https://leetcode.cn/problems/remove-duplicates-from-sorted-list/submissions/

思路

比较简单看代码就可以

AC代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* p = head;
        while (p)
        {
            ListNode* q = p->next;
            if (q && q->val == p->val)
            {
                p->next = q->next;
            }
            else
            {
                p = p->next;
            }
        }
        return head;
    }
};

LeetCode 86. 分隔链表

题目类型

1. 分治

题目链接

https://www.acwing.com/activity/content/problem/content/2435/

思路

1. 定义两个链表，一个存储小于x的数，一个存储大于x的数
2. 从头往后遍历分别插入两个链表
3. 最后将两个链表归并

AC代码

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // 定义两个头结点
        ListNode* l_head = new ListNode(-1), *r_head = new ListNode(-1);
        ListNode* lt = l_head, *rt = r_head;

        for (auto p = head; p; p = p->next)
        {
            if (p->val < x)
            &#123;
                lt->next = p;
                lt = p;
            &#125;
            else
            &#123;
                rt->next = p;
                rt = p;
            &#125;
        &#125;
        lt->next = r_head->next;
        rt->next = nullptr;
        return l_head->next;
    &#125;
&#125;;

LeetCode 92. 反转链表 II

题目类型

1. 链表逆转

题目链接

https://leetcode.cn/problems/reverse-linked-list-ii/

思路

这道题一点点绕 我刚开始也想不出来 第一天大概写了一下然后报错 我就跳过写第二题了
代码思路看下面AC代码的注释即可

AC代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (left == right) return head;
        //创造头结点
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* p = dummy;

        // p找到left的前驱结点 a为left结点的前驱结点 b为left结点 c为left结点的下个结点
        for (int i = 0; i < left - 1; i ++) p = p->next;
        ListNode* a = p, *b = a ->next, *c = b->next;

        // 将left到right的指针反向
        for (int i = left; i < right; i ++) // 内部进行right-left次逆转即可
        &#123;
            ListNode* d = c->next;// 这里要保存好c的next指针 因为c要反向指向b 会丢失下一个结点
            c->next = b;
            // 更新下一次翻转所需要的工作指针
            b = c, c = d;
        &#125;
        // 从left 到 right 已经反转 接下来处理好原来left的前驱和right的后继
        a->next->next = c; // 此时c是right的下一个结点 只需要把left点（即a->next）的next指向c即可
        a->next = b; // 此时b是right点 只需要把left的前驱结点（即a）的next指向b 

        return dummy->next;
    &#125;
&#125;;

LeetCode 109. 有序链表转换二叉搜索树

题目类型

1. 二叉树

题目链接

https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/

思路

每次以链表的中点为根节点，生成二叉树，可以递归处理

AC代码

class Solution {
public:
    // 寻找链表的(left, right)中点 用快慢指针
    ListNode* getMidNode(ListNode* left, ListNode* right)
    {
        ListNode* fast = left;
        ListNode* slow = left;
        while (fast != right && fast->next != right)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    // 以left和right的中点建立一棵二叉子树
    TreeNode* buildBST(ListNode* left, ListNode* right)
    {
        if (left == right) return nullptr;

        // 寻找left到right的中点
        ListNode* mid = getMidNode(left, right);
        // 以mid为中点转变为一棵二叉树
        TreeNode* root = new TreeNode(mid->val);
        root->left = buildBST(left, mid);
        root->right = buildBST(mid->next, right);
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        return buildBST(head, nullptr);
    }
};

LeetCode 114. 二叉树展开为链表

题目类型

1. 链表二叉树

题目链接

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/

思路

看LeetCode的题解就好了 很详细

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/

AC代码一 遍历树

class Solution {
public:
    void flatten(TreeNode* root) {
        while (root)
        {
            TreeNode* p = root->left;
            if (p)
            {
                TreeNode* q = p;
                while (q->right) q = q->right;
                q->right = root->right;
                root->right = p;
                root->left = nullptr;
            }
            root = root->right;
        }
    }
};

AC代码二 先序遍历

LeetCode 116. 填充每个节点的下一个右侧节点指针

题目类型

1. BFS

题目链接

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/submissions/

思路

1. 遍历二叉树的每一层
2. 对于每一层的结点A和下一个结点B，将A的左孩子的next指向A的右孩子，如果B存在，将A的右孩子指向B的左孩子

AC代码

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        // 先存下根节点
        Node* source = root;
        // 遍历树的每一层
        while (root->left)
        {
            // 遍历每一层的每一个结点
            for (Node* p = root; p; p = p->next)
            {
                // 同一父节点 直接让左孩子指向右孩子
                p->left->next = p->right;
                // 不同父节点 让前一个父节点的右孩子指向后一个父节点的左孩子
                // 如果没有下一个结点则无需添加
                if (p->next) p->right->next = p->next->left;
                else p->right->next = NULL;
            }
            root = root->left;
        }
        return source;
    }
};

LeetCode 117. 填充每个节点的下一个右侧节点指针 II

题目类型

1. BFS

题目链接

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii

思路

与前一题不同，该题遍历每一层的时候需要创建head和tail两个指针
head是用来使下一层的结点连接到一条链表中，tail是用来指向该链表的尾结点用于插入
最后更新下一层 cur

AC代码

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        Node* cur = root;
        while (cur)
        {
            Node* head = new Node(-1);
            Node* tail = head;
            // 遍历该层的每一个结点
            for (Node* q = cur; q; q = q->next)
            {
                if (q->left) tail = tail->next = q->left;
                if (q->right) tail = tail->next = q->right;
            }
            cur = head->next;
        }
        return root;
    }
};

LeetCode 141. 环形链表

题目类型

1. 判断环

题目链接

https://leetcode.cn/problems/linked-list-cycle

思路

方法一：
遍历链表，使用哈希表记录访问过的点，如果访问的点出现在哈希表中说明存在环

方法二：
快慢指针，如果slow 和 fast相遇说明存在环

AC代码—哈希表

class Solution {
public:
          bool hasCycle(ListNode *head) {
        // 使用哈希表存储访问过的点
        unordered_set<ListNode*> hash;

        ListNode* p = head;
        while (p)
        &#123;
            if (hash.count(p)) return true;
            hash.insert(p);
            p = p->next;
        &#125;
        return false;
    &#125;
&#125;;

AC代码—快慢指针

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        ListNode* slow = head, * fast = head->next;
        while (slow != fast)
        {
            if (!fast || !fast->next) return false;
            fast = fast->next->next;
            slow = slow->next;
        }
        return true;
    }
};

LeetCode 143. 重排链表

题目类型

1. 链表排序

题目链接

https://leetcode.cn/problems/reorder-list/submissions/

思路

方法一：

1. 由于链表没有随机访问的特性，所以将链表存储在线性表r中
2. 使用双指针对链表重新排序

时间复杂度O(n) 空间复杂度O(n)

方法二：此题可以分为三个子问题

1. 寻找链表中间 参考 LeetCode 876
2. 反转后半段的链表 参考 LeetCode 206
3. 使用两个指针，交叉拼接拼接两个链表

AC代码一

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head) return ;
        vector<ListNode*> r;

        while (head)
        &#123;
            r.push_back(head);
            head = head->next;
        &#125;

        int i = 0, j = r.size() - 1;
        while (i < j)
        &#123;
            r[i ++]->next = r[j];

            if (i == j) break;

            r[j --]->next = r[i];
        &#125;
        r[i]->next = nullptr;
    &#125;
&#125;;

AC代码二

class Solution {
public:
    // 寻找链表的中点
    ListNode* searchMid(ListNode* head)
    {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 反转链表
    ListNode* reverseList(ListNode* head)
    {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur)
        {
            ListNode* curTmp = cur->next;
            cur->next = prev;
            // 保存好下一次反转的前驱结点和下一次反转的当前节点cur
            prev = cur, cur = curTmp;
        }
        return prev;
    }

    // 交叉合并链表
    void mergeList(ListNode* l1, ListNode* l2)
    {
        while(l1 && l2)
        {
            ListNode* l1_tmp = l1->next;
            ListNode* l2_tmp = l2->next;

            l1->next = l2, l1 = l1_tmp;
            l2->next = l1, l2 = l2_tmp;
        }
    }

    void reorderList(ListNode* head) {
        ListNode* mid = searchMid(head);
        // 划分两个链表
        ListNode* l1 = head;
        ListNode* l2 = mid->next;
        mid->next = nullptr;

        // 先反转链表
        l2 = reverseList(l2);

        // 再合并链表
        mergeList(l1, l2);
    }
};

LeetCode 146. LRU缓存机制

题目类型

1. 链表插入
2. 链表删除
3. 双链表
4. 哈希表

题目链接

https://leetcode.cn/problems/lru-cache

思路

此题难度稍微一点点大，主要是题目要求get和put要O(1)，也就是说插入删除查找要O(1) 复杂度，所以利用哈希表和双链表来实现缓存的LRU

1. 可以利用哈希表当做缓存，查找可以实现O(1)
2. 双链表当做缓存的时间队列（最近访问放最前面，最后访问放最后），插入和删除由于有头指针和尾指针，也可以实现O(1)

其他就是常见的业务需求了

AC代码

class LRUCache {
public:
    struct Node
    {
        int key, val;
        Node* left, *right;
        Node(int _key, int _val): key(_key), val(_val), left(NULL), right(NULL) {};
    } *L, *R;
    unordered_map<int, Node*> hash;

    void insert(Node *p)
    &#123;
        p->right = L->right;
        p->left  = L;
        L->right->left = p;
        L->right = p;
    &#125;

    void remove(Node* p)
    &#123;
        p->right->left = p->left;
        p->left->right = p->right;
    &#125;
    int n;
    LRUCache(int capacity) &#123;
        n = capacity;
        L = new Node(-1, -1), R = new Node(-1, -1);
        L->right = R;
        R->left = L;
    &#125;

    int get(int key) &#123;
        // 若不在缓存
        if (hash.count(key) == 0) return -1;

        auto p = hash[key];
        remove(p), insert(p);
        return p->val;

    &#125;

    void put(int key, int value) &#123;
        // 若在缓存中 覆盖val值 并更新链表
        if (hash.count(key))
        &#123;
            auto p = hash[key];
            p->val = value;
            remove(p), insert(p);
        &#125;
        else
        &#123;
            if (hash.size() == n) // 如果缓存满了 删除最少访问的那个
            &#123;
                auto p = R->left;
                remove(p);
                hash.erase(p->key);
            &#125;
            auto p = new Node(key, value);
            insert(p), hash[key] = p;
        &#125;
    &#125;
&#125;;

LeetCode 147. 对链表进行插入排序

题目类型

1. 插入排序

题目链接

https://leetcode.cn/problems/insertion-sort-list

思路

看起来简单，我写的时候容易被指针搞乱，基础还是不扎实

1. 创建虚拟结点dummy，用于存放结果
2. p指针遍历原链表，cur遍历结果链表
3. 寻找第一个比p大的结点，将cur插在p的前面

AC代码

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* dummy = new ListNode(-1);

        // 遍历链表
        for (auto p = head; p;)
        {
            // 从结果链表的开头也就是dummy开始往后寻找
            auto cur = dummy, p_next_tmp = p->next;
            // 寻找结果链表的第一个大于p的结点 将p放在该结点的前面
            while (cur->next && p->val >= cur->next->val) cur = cur->next;
            p->next = cur ->next;
            cur->next = p;
            p = p_next_tmp;
        }
        return dummy->next;
    }
};

LeetCode 148. 排序链表

题目类型

1. 归并

题目链接

https://leetcode.cn/problems/sort-list/

思路

先跳过吧 这题我不会做。。。

AC代码

LeetCode 160. 相交链表

题目类型

1. 技巧题

题目链接

https://leetcode.cn/problems/intersection-of-two-linked-lists/

思路

AC代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p = headA, *q = headB;
        while (p != q)
        {
            if (p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        return p;
    }
};

LeetCode 203. 移除链表元素

题目类型

1. 链表删除

题目链接

https://leetcode.cn/problems/remove-linked-list-elements/

思路

思路简单 找到删除点 用链表删除就可以了
注意一下删除节点是head的情况 新创建一个虚拟头结点即可

AC代码

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        for (auto p = dummy; p;)
        {
            if (p->next && p->next->val == val) 
                p->next = p->next->next;
            else
                p = p->next;
        }
        return dummy->next;
    }
};

LeetCode 206. 反转链表

题目类型

1. 迭代

题目链接

https://leetcode.cn/problems/reverse-linked-list/

思路

画图看比较简单
遍历链表，每次记录好cur结点的后继结点，再将cur指向cur的前驱结点，以此迭代下去

AC代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur  = head;
        while (cur)
        {
            ListNode* curNextTmp = cur->next;
            cur->next = prev;
            prev = cur, cur = curNextTmp;
        }
        return prev;
    }
};

LeetCode 234. 回文链表

题目类型

1. 反转链表

题目链接

https://leetcode.cn/problems/palindrome-linked-list/

思路

参考 LeetCode 206. 反转链表

1. 链表的后半部分反转
2. 使用双指针从链头和链尾往前判断
3. 最后记得把链表恢复原状

时间复杂度O（n）
空间复杂度O（1）

AC代码

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int n = 0;
        for (auto p = head; p; p = p->next) n ++;
        if (n <= 1) return true;
        int half = n / 2;

        // 反转链表
        ListNode* a = head;
        for (int i = 0; i < n - half; i ++) a = a->next; // 将指针a指向翻转点
        ListNode* b = a->next;
        while (b)
        &#123;
            ListNode* c = b->next;
            b->next = a;
            a = b, b = c;
        &#125;

        // 判断是否是回文数
        bool success = true;
        ListNode* p = head, * q = a;
        for (int i = 0; i < half; i ++) // 比较half次
        &#123;
            if (p->val != q->val)
            &#123;
                success = false;
                break;
            &#125;
            p = p->next, q = q->next;
        &#125;

        // 恢复链表
        ListNode* tail = a;
        b = a->next;
        for (int i = 0;i < half - 1; i ++)
        &#123;
            ListNode* c = b->next;
            b->next = a;
            a = b, b = c;
        &#125;
        tail->next = nullptr;
        return success;
    &#125;
&#125;;

LeetCode 237. 删除链表中的节点

题目类型

1. 删除

题目链接

https://leetcode.cn/problems/delete-node-in-a-linked-list/

思路

两行代码就可以

1. 由于无法知道前驱结点 所以将下一个结点的值复制到当前节点
2. 再删除下一个结点即可

AC代码

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

LeetCode 876. 链表的中间结点

题目类型

1. 快慢指针

题目链接

https://leetcode.cn/problems/middle-of-the-linked-list/

思路

比较简单 双指针问题 直接看代码就行

AC代码

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

LeetCode 328. 奇偶链表

题目类型

1. 插入
2. 合并

题目链接

https://leetcode.cn/problems/odd-even-linked-list

思路

分为两个链表，最后拼接即可

AC代码

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        // 只有一个或两个元素直接返回原链表
        if(!head || !(head->next)) return head;

        // 定义奇数链表和偶数的链表的头结点和尾结点
        ListNode* oh = head, * ot = oh;
        ListNode* eh = head->next, * et = eh;

        for (ListNode* p = head->next->next; p;)
        {
            ot = ot->next = p;
            p = p->next;
            if (p)
            {
                et = et->next = p;
                p = p->next;
            }
        }
        ot->next = eh;
        et->next = nullptr;
        return oh;
    }
};

LeetCode 445. 两数相加 II

题目类型

1. 高精度加法

题目链接

https://leetcode.cn/problems/add-two-numbers-ii/

思路

由于这是链表，又为了人为习惯故意让结点从高位到低位，但不利于计算，所以这里需要反转链表

1. 反转两个链表l1 l2
2. 依次遍历两个链表，使用进位变量c，存储同一位的两个结点相加的结果
3. 将结果取余放入结果链表中，进位变量c也要修改

AC代码

class Solution {
public:
    ListNode* reverse(ListNode* head)
    {
        ListNode* prev = nullptr, *cur = head;
        while (cur)
        {
            ListNode* cur_tmp_next = cur->next;
            cur->next = prev;
            prev = cur, cur = cur_tmp_next;
        }
        return prev;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1), l2 = reverse(l2);

        // 存放结果
        ListNode* res_dummy = new ListNode(-1);
        int c = 0;
        while (l1 || l2 || c)
        {
            if (l1) c += l1->val, l1 = l1->next;
            if (l2) c += l2->val, l2 = l2->next;
            ListNode* cur = new ListNode(c % 10);
            c /= 10;
            // 使用头插法
            cur->next = res_dummy->next;
            res_dummy->next = cur;
        }
        return res_dummy->next;
    }
};

LeetCode 725. 分隔链表

题目类型

1. 分段

题目链接

https://leetcode.cn/problems/split-linked-list-in-parts/

思路

将n个结点的链表分为k份， n % k == c

1. 如果c == 0，说明刚刚好分，或者前面几个链表有结点，最后几个没有结点（即k> n的情况）
2. 如果c != 0，则每个链表分配len = n/k结点外，前c个链表再分配一个结点

AC代码

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) &#123;
        int n = 0;
        for (auto p = head; p; p = p->next) n ++;

        vector<ListNode*> res;
        auto p = head;

        for (int i = 0; i < k; i ++)
        &#123;
            // 当前链表长度len
            int len = n / k;
            // 前n % k个链表多1个
            if (i + 1 <= n % k) len ++;

            res.push_back(p);
            for (int j = 0; j < len - 1; j ++) p = p->next;

            if (p)
            &#123;
                auto q = p->next;
                p->next = nullptr;
                p = q;
            &#125;
        &#125;
        return res;
    &#125;
&#125;;

##

题目类型

1. 题目链接

思路

AC代码

##【未完待更】