LeetCode刷题链表

链表总结 + 常用技巧

1. 画图 = 直观 + 形象 + 便于理解
2. 引入虚拟头节点，便于处理边界情况，方便我们对链表进行操作

3. 大胆去定义变量，不要吝啬空间，可以简单化链表链接

4. 快慢双指针，判断环，找链表中环的入口，找链表中倒数第n个节点
5. 链表中的常用操作：
   创建一个新节点 new
   尾插
   头插，使用虚拟头节点，例题逆序链表，如下图

两数相加

题目链接

题解

1. 在链表中模拟两数相加的过程
2. 注意t的进位，一个链表比另一个链表长的情况，开虚拟头结点，我们模拟相加的时候从低位开始加，这里刚好是从低位开始加的，不需要逆置链表

代码

class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        // 记录第一个链表和第二个链表
        ListNode* cur1 = l1,*cur2 = l2;
        ListNode* newhead = new ListNode(0);// 哨兵位节点
        int t = 0;// 记录进位
        ListNode* pcur = newhead;// 尾指针
        
        // cur1,cur2,t都不为空
        while(cur1 || cur2 || t)
        {
            // 加上第一个链表
            if(cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            // 加上第二个链表
            if(cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            pcur->next = new ListNode(t % 10);
            pcur = pcur->next;
            t /= 10;
        }    
        
        // 防止内存泄漏
        pcur = newhead->next;
        delete newhead;

        return pcur;
    }
};

两两交换链表中的节点

题目链接

题解

1. 模拟
2. 创建4个变量，一个虚拟节点，最后只需返回虚拟节点的next指针，然后交换两数的指针，让指针移动到下一个要交换的位置
3. 注意数为奇数和偶数的情况，为偶数时cur指针为空，为奇数的时候next指针为空

代码

class Solution 
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if(head == nullptr) return nullptr;
        if(head->next == nullptr) return head;
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        ListNode* cur = head;
        ListNode* next = cur->next;
        ListNode* nnext = next->next;


        while(cur && next)
        {
            // 交换节点
            prev->next = next; 
            next->next = cur;
            cur->next = nnext;
            
            // 修改指针并且注意顺序
            prev = cur;
            cur = nnext;
            if(cur == nullptr) break;
            next = nnext->next;
            if(next == nullptr) break;
            nnext = next->next;
        }
        
        cur = newhead->next;
        delete newhead;
           
        return cur;
    }
};

重排链表

题目链接

题解

1. 模拟
2. 先找到链表的中间节点，slow->next为分割点分割两个链表，利用头插法逆置后面的一个链表，最后按顺序链接两个链表

利用快慢双指针分割链表

头插法

代码

class Solution 
{
public:
    void reorderList(ListNode* head) 
    {
        // 快慢双指针找链表的中间节点
        // 0个1个2个节点不需要重排
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
        
        ListNode* slow = head;
        ListNode* fast = head;
        // 奇数个节点和偶数个节点
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 把slow->next做为分割链表的节点
        // 方便分割链表
        // 否则slow做为分割节点,还需要加入虚拟节点,也还是是slow->next

        // 头插法进行分割链表
        // 逆置第二个链表
        ListNode* head2 = new ListNode(0);
        ListNode* cur = slow->next;
        slow->next = nullptr;
        
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }

        // 尾插法连接两个链表
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        ListNode* cur1 = head,*cur2 = head2->next;
        // 第一个链表比第二个链表长
        while(cur1)
        {
            prev->next = cur1;
            cur1 = cur1->next;
            prev = prev->next;

            if(cur2)
            {
                prev->next = cur2;
                cur2 = cur2->next;
                prev = prev->next;
            }
        }
        delete head2;
        delete newhead;
    }
};

合并k个升序链表

题目链接

题解

代码

class Solution 
{
    struct cmp
    {
        bool operator()(const ListNode* l1,const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 创建一个小根堆
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
        
        // 让所有的头结点进入小根堆
        for(auto& x : lists)
        {
            if(x) heap.push(x);
        }

        ListNode* newhead = new ListNode(0);
        ListNode* cur = newhead;
        while(!heap.empty())
        {
            ListNode* t = heap.top();
            cur->next = t;
            heap.pop();
            cur = cur->next;
            if(t->next) heap.push(t->next); 
        }
        cur = newhead->next;
        delete  newhead;

        return cur;
    }
};

K个一组翻转链表

题目链接

题解

1. 注意每次更新一下prev这个指针，prev = tmp

代码

class Solution 
{
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        // 先算出有多少个节点
        int count = 0;
        ListNode* cur = head;
        while(cur)
        {
            count++;
            cur = cur->next;
        }
        
        // 头插法
        int p = count / k;
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        cur = head;
        for(int i = 0;i < p;i++)
        {
            ListNode* tmp = cur; 
            for(int j = 0;j < k;j++)
            {
                ListNode* next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev->next = cur;

        prev = newhead->next;
        delete newhead;

        return prev;
    }
};