算法：常见的链表算法

本篇总结常见的链表算法题和看他人题解所得到的一些收获

链表算法

关于链表的算法：

1. 画图：画图可以解决绝大部分的数据结构的问题，任何的算法题借助图都可以有一个比较清晰的思路
2. 引入哨兵位头节点：头节点可以避免处理很多边界情况，在解决一些问题前很方便
3. 多定义几个变量：可以很方便的解决问题
4. 快慢指针：在处理带环的问题，环的入口，倒数节点的时候很好用

两数相加

在这里积累这个题的目的是学习代码的写法，学习他人的代码

这是自己的代码：

class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* newhead = new ListNode();
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* cur = newhead;
        int carry = 0, sum = 0, ret = 0;

        while(cur1 && cur2)
        {
            // 计算出这个节点要存的值是多少
            sum = cur1->val + cur2->val + carry;
            carry = sum / 10;
            ret = sum % 10;
            
            // 插入节点
            ListNode* newnode = new ListNode(ret);
            cur->next = newnode;
            cur = newnode;

            // 迭代
            cur1 = cur1->next;
            cur2 = cur2->next;
        }

        while(cur1)
        {
            // 计算出这个节点要存的值是多少
            sum = cur1->val + carry;
            carry = sum / 10;
            ret = sum % 10;

            // 插入节点
            ListNode* newnode = new ListNode(ret);
            cur->next = newnode;
            cur = newnode;

            // 迭代
            cur1 = cur1->next;
        }

        while(cur2)
        {
            // 计算出这个节点要存的值是多少
            sum = cur2->val + carry;
            carry = sum / 10;
            ret = sum % 10;

            // 插入节点
            ListNode* newnode = new ListNode(ret);
            cur->next = newnode;
            cur = newnode;

            // 迭代
            cur2 = cur2->next;
        }

        if(carry)
        {
            // 插入节点
            ListNode* newnode = new ListNode(carry);
            cur->next = newnode;
            cur = newnode;
        }

        return newhead->next;
    }
};

运行可以通过，但是代码量比较冗余，其实可以发现while循环和后面的if语句有相当多的相似语句，因此看下面的代码：

class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* newhead = new ListNode();
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* cur = newhead;
        int sum = 0;

        while(cur1 || cur2 || sum)
        {
            // 先加第一个链表
            if(cur1)
            {
               sum += cur1->val;
               cur1 = cur1->next;
            }

            // 再加第二个链表
            if(cur2)
            {
                sum += cur2->val;
                cur2 = cur2->next;
            }

            // 处理节点数据
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            sum /= 10;
        }

        // 处理掉不必要的内存空间
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};

两两交换链表中的节点

其实这个题已经见过很多次了，有很多种解决方法，直接模拟，递归…

但是这里积累它的意义在于，引入虚拟头节点对于解题是很有帮助的

/**
 * 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();
        newhead->next = head;
        ListNode* prev = newhead;
        ListNode* cur = newhead->next;
        ListNode* next = cur->next;
        ListNode* nnext = next->next;
        while(cur && next)
        {
            // 交换节点
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

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

        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

不带虚拟头节点：

/**
 * 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 = head->next;
        // 找到当前待交换的两个节点
        ListNode* left = head;
        ListNode* right = head->next;
        while(left && right)
        {
            // 交换两个节点
            left->next = right->next;
            right->next = left;
            // 进行迭代
            ListNode* prev = left;
            left = left->next;
            if(left)
            {
                right = left->next;
                if(right)
                    prev->next = right;
            }
        }

        return newhead;
    }
};

递归解题

/**
 * 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* left = head;
        ListNode* right = left->next;
        ListNode* tmp = right->next;
        right->next = left;
        left->next = swapPairs(tmp);
        return right;
    }
};

重排链表

积累本题的意义在于，本题综合了逆序链表，快慢指针，链表插入的问题，是一个综合性的题

/**
 * 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) 
    {
        // 利用快慢双指针找到中间节点
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 得到两个新链表
        ListNode* newheadleft = head;
        ListNode* newheadright = Reverse(slow->next);
        slow->next = nullptr;

        // 把这两个链表再组装起来
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        ListNode* cur1 = newheadleft;
        ListNode* cur2 = newheadright;
        while(cur1 || cur2)
        {
            if(cur1)
            {
                tail->next = cur1;
                tail = tail->next;
                cur1 = cur1->next;
            }
            if(cur2)
            {
                tail->next = cur2;
                tail = tail->next;
                cur2 = cur2->next;
            }
        }

        ListNode* res = newhead->next;
        delete newhead;
        head = res;
    }

    ListNode* Reverse(ListNode* head)
    {
        ListNode* newhead = new ListNode();
        ListNode* cur = head;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
        }

        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

合并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) 
    {
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        for(int i = 0; i < lists.size(); i++)
        {
            merge(newhead->next, lists[i]);
        }
        return newhead->next;
    }

    void merge(ListNode*& head, ListNode* cur)
    {
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        while(head && cur)
        {
            if(head->val < cur->val)
            {
                tail->next = head;
                tail = tail->next;
                head = head->next;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
                cur = cur->next;
            }
        }
        if(head) tail->next = head;
        if(cur) tail->next = cur;

        head = 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:
    struct cmp
    {
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
    // 利用优先级队列进行优化
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        
        // 把每一个链表都塞进去
        for(int i = 0; i <lists.size(); i++)
        {
            if(lists[i])
                pq.push(lists[i]);
        }
        
        // 创建虚拟头节点，开始链入到链表中
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;

        // 找到最小的节点，拿出来，再把它的下一个节点再塞进去，直到队列为空
        while(!pq.empty())
        {
            ListNode* top = pq.top();
            pq.pop();
            if(top != nullptr)
            {
                ListNode* next = top->next;
                top->next = nullptr;
                // 塞到目标链表中
                tail->next = top;
                tail = tail->next;
                // 再把剩下的部分再塞进去
                if(next)
                    pq.push(next);
            }
        }

        // 返回信息
        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

利用归并的思想解题

/**
 * 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) 
    {
        return merge(lists, 0, lists.size() - 1);
    }

    // 归并排序
    ListNode* merge(vector<ListNode*>& lists, int left, int right)
    {
        // 处理特殊情况
        if(left > right) return nullptr;
        if(left == right) return lists[left];

        // 拆分数组
        int midi = left + (right - left) / 2;
        // [left, midi][midi + 1, right]
        ListNode* l1 = merge(lists, left, midi);
        ListNode* l2 = merge(lists, midi + 1, right);

        // 排序
        return mergetwonode(l1, l2);
    }

    // 合并链表
    ListNode* mergetwonode(ListNode* l1, ListNode* l2)
    {
        ListNode* newhead = new ListNode();
        ListNode* cur1 = l1, *cur2 = l2, *tail = newhead;
        
        while(cur1 && cur2)
        {
            if(cur1->val <= cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
                tail = tail->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
                tail = tail->next;
            }
        }

        if(cur1) tail->next = cur1;
        if(cur2) tail->next = cur2;

        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

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 
{
    // 思路：把链表k个一组拿出来，再翻转，再链入一个新的链表中
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        ListNode* left = head, *right = left;

        while(left && right)
        {
            // 把链表k个一组分出来
            for(int i = 1; i < k; i++)
            {
                // 如果此时已经到最后了，那么这最后一组就不需要进行翻转
                if(right == nullptr)
                {
                    tail->next = left;
                    return newhead->next;
                }
                right = right->next;
            }
            // 断链
            if(right)
            {
                ListNode* newleft = right->next;
                right->next = nullptr;
                // 现在从[left, right]就是一段完整的不带头节点的链表了
                // 把这段链表进行翻转，并链入到新的链表中
                tail->next = reverse(left);
                tail = left;
                // 迭代，找下一组k个节点
                left = newleft, right = left;
            }
        }
        tail->next = left;
        return newhead->next;
    }

    // 进行链表的反转
    ListNode* reverse(ListNode* cur)
    {
        ListNode* newhead = new ListNode();
        
        // 把链表中的节点头插到新链表中
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
        }

        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

这个题的难点在于细节问题的处理，其实思路并不难

总结

其实对于链表这一块的算法主要是体现在需要处理一些边界情况和循环调用带来的问题，通过借助虚拟头节点和多创建几个指针可以缓解这种情况，主要是细节要处理好，对于思维的需求没有那么高文章来源地址https://www.toymoban.com/news/detail-835452.html

到了这里，关于算法：常见的链表算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！