【优选算法】链表

链表常用的技巧和操作

1、常用技巧

1. 画图

2. 引入虚拟头结点

   • 便于我们处理边界情况
   • 方便我们对链表进行操作

3. 不要吝啬空间，大胆定义变量
   相信我们在上学期间学习过数据结构的同学都很熟悉，给你两个节点，使用双向链接将其链接起来，但是只给你一个节点的地址，要求你在两个节点之间插入一个新节点，大家可能都被链接的顺序恶心过，但是只要定义一个变量记录另一个节点的地址，那么我们想怎么链接就怎么链接了。

4. 快慢双指针

2、常用操作

1. 创建一个新节点
2. 头插
3. 尾插

一、两数相加

题目描述：

思路讲解：
本道题只需要模拟两数相加的过程即可，首先定义一个虚拟头结点，这样就不需要对链表进行特殊处理，然后定义两个变量分别记录对应位上两数相加的个位和进位，创建一个节点存储个位上的数字，尾插到虚拟头结点所在的链表中，然后同时将两个原始链表向后同时移动，重复上面的操作，直到两个链表都遍历完后返回以虚拟头结点后面一个节点为头结点的链表即完成本题。

需要注意两数相加时还要加上进位，若是某个链表对应位上没有节点，我们认定这个节点上的数字为0。

编写代码：

/**
 * 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) {
        int add = 0;
        ListNode* newhead = new ListNode();
        ListNode* cur = newhead;
        while(l1 || l2 || add)
        {
            int num1 = (l1 != nullptr) ? l1->val : 0;
            int num2 = (l2 != nullptr) ? l2->val : 0;

            int sum = num1 + num2 + add;
            ListNode* newNode = new ListNode(sum % 10);
            cur->next = newNode;
            cur = cur->next;
            add = sum / 10;

            if(l1 != nullptr)   l1 = l1->next;
            if(l2 != nullptr)   l2 = l2->next;
        }

        return newhead->next;
    }
};

二、两两交换链表中的节点

题目描述：

思路讲解：
本道题我们需要做的就是将链表中每两个节点进行交互即可，我们只需要模拟如何将节点进行交换即可。若链表中只有一个节点时，不需要进行交换，返回即可。

这里我创建一个虚拟头结点用来避免对链表第一次交换进行特殊处理，通过画图我们发现，看似是对两个节点进行交换，实际上却涉及到了四个节点，为了我们方便处理，直接定义四个指针分别指向四个连续的节点，有了这四个指针就可以很方便的将两个节点进行交换了，如下图，我们只需要修改prve、cur和next指向节点中next的指向即可，修改完指向后就需要指针向后移动了，各个指针移动后对应的位置在下图中有明确的标识，有些指针移动后位置比较特殊，需要特殊判断。

然后就是循环的判断条件了，这里我们将链表分类奇数节点个数和偶数节点个数来看，如图，奇数情况下只要next没有指向节点就结束，偶数情况下cur没有指向节点就结束，综上只要cur或next有一个没有指向节点就结束循环。最后返回以虚拟头结点后面一个节点为头结点的链表即完成本题。

编写代码：

/**
 * 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) {
        if(head == nullptr || head ->next == nullptr)
            return head;

        ListNode* newhead = new ListNode();
        ListNode* prev = newhead ,*cur = head ;
        ListNode* next = head->next , *nnext = next->next;

        while(cur != nullptr && next != nullptr)
        {
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

            prev = cur;
            cur = nnext;
            
            if(cur)
                next = cur->next;
            if(next)
                nnext = next->next;
        }

        return newhead->next;
    }
};

三、重排链表

题目描述：

思路讲解：

本道题是让我们将链表重新排序，并且不能只修改节点的值，而是要进行节点之间的切换，我们看了题目的示例，可以得出重排链表，实际上是重复拿出原链表中的头节点和尾节点，并将尾节点链接到头节点的后面，然后按照拿出来的顺序进行链接，即可完成对链表的重排。

本题还有一个更简单的思路，就是将这个链表从中间分开变为两个链表，使前面链表的节点个数比后面的链接节点个数多一个或是相等，然后将后面这个链表逆转，最后通过两个链表的合并即可完成链表的重排。

编写代码：

/**
 * 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:
    void reorderList(ListNode* head) {
        if(head->next == nullptr)
            return;

        ListNode* slow = head , *fast = head -> next;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 从中间截断为两段链表
        ListNode* newhead1 = new ListNode();
        ListNode* cur = slow -> next;

        slow->next = nullptr;
        ListNode* next = cur->next;

        // 逆置后半段链表
        cur->next = nullptr;
        while(cur)
        {
            cur->next = newhead1->next;
            newhead1 -> next = cur;
            cur = next;

            if(next)
                next = next -> next;
        }

        ListNode* cur1 = head ,*cur2 = newhead1->next;
        ListNode* next1 = head->next ,*next2 = cur2->next;

        ListNode* newhead2 = new ListNode();
        cur = newhead2;
        while(cur2)
        {
            // 依次插入两个链表
            cur -> next = cur1;
            cur1 = next1;
            if(next1)
                next1 = next1->next;
            cur = cur -> next;

            cur -> next = cur2;
            cur2 = next2;
            if(next2)
                next2 = next2->next;
            cur = cur -> next;
        }
        
        // 第一段链表一定与第二段链表等长或更长
        if(cur1)
            cur->next = cur1;

        head = newhead2;
    }
};

四、合并 K 个升序链表

题目描述：

思路讲解：
本道题是想让我们将k个升序链表，按照节点的大小合并为1个升序链表，这里我们一定能想到的就是暴力解法，每次遍历所以链表的头节点，找到最小的节点并取出，再将这个节点链入到新链表中，重复这样的操作，直到k个链表中没有任何节点位置，最后返回新链表即可完成本道题，这样完成本道题的时间复杂度为O(nk${}^2$)。

这里可以使用优先级队列进行优化，我们创建一个小堆，将所有链表的头节点放入小堆中，小堆根据节点的大小将最小的节点移动到堆顶，这样我们就可以通过找到堆顶元素就可以找到k个链表中头节点中最小的节点了，将该节点从堆中和它所对应的链表中取出，并将它所对应链表中的新头节点放入到堆中，若没有节点则不需加入，小堆则会按照它的特性将堆中的节点重新调整，然后将取出来的节点链接到新的链表中，重复这样的操作直到堆中没有任何节点为止，最后将新链表返回即可完成合并 K 个升序链表。

编写代码：

/**
 * 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* mergeKLists(vector<ListNode*>& lists) {
        int count = lists.size(); // 链表的个数
        ListNode* newhead = new ListNode();
        ListNode* last = newhead;
        // 记录链表中有节点的链表个数
        int ListCount = 0;

        while(1)
        {
            int MinPos = 0;
            int min = 10001;

            for(int i = 0 ; i < count; i++)
            {
                ListNode* cur = lists[i];

                if(cur)
                {   
                    ListCount++;
                    if(min > cur->val)
                    {
                        min = cur->val;
                        MinPos = i;
                    }
                }
            }

            // 当链表所有链表都没有节点时跳出循环
            if(ListCount == 0)
                break;
            last->next = lists[MinPos];
            // 插入到新的链表中
            last = last -> next;

            if(lists[MinPos])
                lists[MinPos] = lists[MinPos]->next;
            MinPos = 0 , ListCount = 0;
        }

        return newhead->next;
    }
};

五、K 个一组翻转链表

题目描述：

思路讲解：
本道题想让我们将链表中每k个节点进行翻转，若剩下的节点小于k个则保持愿意。

这里可以使用模拟的思路解决本题，我们先遍历整个链表，得到链表中节点的个数为num，有每k个节点需要翻转一次，通过num/k得到有count组子链表需要翻转。循环count次，每次记录该组子链表的前一个节点和后一个节点，将本组k个节点进行逆序，再链接回原链表中，这里可以使用头插法的方式将链表进行逆序，最后返回链表的头结点即可。

编写代码：

/**
 * 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) {
        int numNode = 0;  // 节点个数
        ListNode* cur = head;

        while(cur)
        {
            numNode++;
            cur = cur->next;
        }

        int opCount = numNode / k;  // 记录需要翻转的次数
        ListNode* newhead = new ListNode();   // 创建哨兵位头结点
        newhead->next = head;
        ListNode* prev = newhead; // 标记每k个节点的前一个节点，方便链接
        cur = head;
        ListNode* connect = cur; // 旋转k个节点后的最后一个节点，方便链接
        ListNode* next = cur->next; 
        while(opCount--)
        {
            connect = cur;
            for(int i = 1 ; i <= k ; i++)
            {
                cur->next = prev->next;
                prev->next = cur;

                cur = next;
                if(next)
                    next = next->next;
            }
            
            // 记录前一段的尾
            prev = connect;
        }

        prev->next = cur;
        return newhead->next;
    }
};

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹