[数据结构与算法]【刷爆LeetCode】六月算法集训（12）链表

题目来源于知识星球—英雄算法联盟，六月算法集训专题

前言

跟随英雄算法联盟博主—英雄哪里出来，每天完成相应的算法练习，一个月后，必定会有所成长！

一、328.奇偶链表（中等）

1.题目描述

2.解题思路

将链表转换成数组直接访问下标即可。

3.代码演示（C++）

class Solution 
{
public:
    ListNode* oddEvenList(ListNode* head) 
    {
        int i;
        ListNode *virtualHead;
        vector<ListNode*> tmp;
        while(head) 
        {
            tmp.push_back(head);
            head = head->next;
        }
        virtualHead = new ListNode();
        head = virtualHead;
        for(i = 0; i < tmp.size(); i += 2) 
        {
            head->next = tmp[i];
            head = head->next;
        }
        for(i = 1; i < tmp.size(); i += 2) 
        {
            head->next = tmp[i];
            head = head->next;
        }
        head->next = NULL;
        return virtualHead->next;
    }
};

4.题目链接

题目传送门

二、725.分隔链表（中等）

1.题目描述

2.解题思路

先计算链表长度l。令a=l/k; b=l%k;对前b个结果链表需要a+1个元素，
后k-b个结果链表需要a个元素，从原链表获取。

3.代码演示（C++）

class Solution 
{
    int Count(ListNode *head) 
    {
        int cnt = 0;
        while(head) 
        {
            head = head->next;
            ++cnt;
        }
        return cnt;
    }

public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) 
    {
        int i;
        vector<ListNode*> ret;
        int cnt = Count(head);
        int per = cnt / k;
        int rem = cnt % k;
        ListNode *virtualHead = new ListNode();
        virtualHead->next = head;
        ListNode *pre = virtualHead;
        
        for(i = 0; i < rem; ++i) 
        {
            ret.push_back(head);
            int c = per + 1;
            while(c--) 
            {
                pre = head;
                head = head->next;
            }
            if(pre) 
            {
                pre->next = NULL;
            }
        }
        for(i = 0; i < k - rem; ++i) 
        {
            ret.push_back(head);
            int c = per;
            while(c--) 
            {
                pre = head;
                head = head->next;
            }
            if(pre) 
            {
                pre->next = NULL;
            }
        }
        return ret;
    }
};

4.题目链接

题目传送门

三、817.链表组件（中等）

1.题目描述

2.解题思路

下次再战！

3.代码演示（C++）

4.题目链接

题目传送门

四、622.设计循环队列（中等）

1.题目描述

2.解题思路

后会有期！

3.代码演示（C++）

4.题目链接

题目传送门

总结

每天跟随英雄哥学习相关的算法，一个月会收获很多，如果你想了解更多关于知识星球的内容，欢迎联系我！