【算法】链表题的常用技巧及算法题（C++）

1. 常用技巧 && 操作

下面的技巧通过一些后面的例题可以较好的理解熟练。

常用技巧

1. 画图
   • 链表题通过画图可以较为直观分析链表，方便分析如何进行对链表的操作等
2. 引入虚拟“头”节点
   • 虚拟节点适合处理一些边界情况
   • 同时放便我们进行对链表的操作
3. 多定义变量
   • 多定义变量增强可读性，也方便自己写代码时的思路
   • 如当频繁使用cur节点的next时，直接定义 ListNode* next = cur->next; 不用再频繁对cur->next进行操作（这个例子较为简单，对于偏复杂的情况有大优点）
   • 不用过于在意这一点空间开销
4. 双指针
   • 如快慢双指针可以解决链表判环、找环入口等。
5. 常用操作
   • 头插 - “反转链表等题，可以解题”
   • 尾插

2. 根据技巧 小试牛刀

下面的题目难度不算太高，就用文字描述的形式解释思路、原理。

141.环形链表

思路

• 解法：即前面介绍过的快慢双指针。

• 解法原理：快指针每次移动两步，而慢指针每次移动一步。如果链表中存在环，那么快指针相对于慢指针的速度差是一定的，因此快指针会逐渐靠近慢指针，最终追上它们。如果链表中不存在环，那么快指针会先到达链表的末尾。

代码

bool hasCycle(ListNode *head) {
    // 快慢指针
    ListNode* slow = head, *fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast =  fast->next->next;
        if(slow == fast)    return true;
    }
    return false;
}

---

142.环形链表II

思路

• 解法：快慢双指针
  1. 同理我们首先 判断链表是否存在环
  2. 当链表存在环则：
     • 让相遇位置节点与头节点依次向后移，直到两节点相遇
     • （也可以将慢指针重新指向头节点，随后快慢指针依次后移一步）

原理分析：我们设链表头节点到环入口节点的距离为a，环入口节点到相遇节点的距离为b，相遇节点到环入口节点的距离为c，则有以下关系：快指针走过的距离是慢指针的两倍，即2(a+b)=a+b+c+b，化简得到a=c。因此，在快慢指针相遇之后，让快指针重新指向头节点，然后快慢指针同时以相同的速度向前移动，当它们再次相遇时所在的节点就是环的入口节点。

代码

ListNode *detectCycle(ListNode *head) {
    if(head == nullptr || head->next == nullptr) return nullptr;
    
    ListNode* slow = head, *fast = head;
    // 先判断是否有环
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            ListNode* meet = slow; // 相遇位置设为meet
            while(meet != head)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return nullptr;
}

---

19.删除链表的倒数第N个结点

思路

• 解法：快慢双指针
  1. 让快指针向前移动n步，使得快指针与慢指针之间相隔n个节点。
  2. 同时移动快指针和慢指针，直到 fast到达链表的末尾 （即为空）。此时slow指向的节点就是要删除的节点的前一个节点 （倒数第n-1）。
  3. 此时将slow指向的节点的next指针指向下下个节点，即跳过待删除节点。

代码

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* PNode = new ListNode(0); // 虚拟头节点
    PNode->next = head;
    ListNode* slow = PNode, *fast = PNode;
    // fast先走n+1步
    for(int i = 0; i < n+1; ++i)
        fast = fast->next;
    // 两指针同步走
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    // 此时slow就是倒数第n-1节点
    slow->next = slow->next->next;
    return PNode->next;
}

---

LCR024.反转链表

思路

• 解法：虚拟头指针+头插
  1. 我们首先创建虚拟头指针newhead，作为最终反转后的链表头节点
  2. 通过将原链表中的节点依次提取头插到新链表中，当cur指向空，此时newhead就是新链表的头

代码

ListNode* reverseList(ListNode* head) {
    ListNode* newhead = nullptr; // 虚拟头指针
    ListNode* cur = head; 

    // 利用头插翻转
    while(cur)
    {
        ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }

    return newhead;
}

---

3. 解决算法题

2.两数相加

思路

如上图所示：

代码

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int t = 0; // 记录相加和
    ListNode* newhead = new ListNode(0); // 虚拟头节点
    ListNode* cur1 = l1, *cur2 = l2; // 用于遍历链表
    ListNode* prev = newhead; // 尾指针
    while(cur1 || cur2 || t)
    {
        // 相加并移动指针 
        if(cur1){
            t += cur1->val;
            cur1 = cur1->next;
        }
        if(cur2){
            t += cur2->val;
            cur2 = cur2->next;
        }

        // 更新结果
        prev->next = new ListNode(t % 10);
        prev = prev->next;
        t /= 10;
    }
    // 释放空间
    prev = newhead->next;
    delete newhead;

    return prev;
}

---

24.两两交换链表中的节点

思路

这里我们提供两种解法：① 递归 ② 循环（模拟过程）

• 解法一：递归

  

  • 根据图中思路，两两交换节点后，新头节点应该是之前在后面的节点
  1. 我们首先记录新头节点节点，后更改指针朝向，将新头节点的next指向下一位的新头节点
  2. 函数的返回结果就是每次的新头节点，利用递归即tmp = swapPairs(head->next->next)，即交换后面的节点并每次链接新头节点

代码

ListNode* swapPairs(ListNode* head) {
    if(head == nullptr || head->next == nullptr)
        return head;
    // 递归
    
    auto tmp = swapPairs(head->next->next); // 翻转后的前一位节点
    auto ret = head->next; // 新头节点
    head->next->next = head; // 更改指针指向
    head->next = tmp;

    return ret;
}

• 解法二：循环

  

  1. 思路如图所示，我们首先定义四个指针（首先创建一个虚拟头节点）
  2. 根据四个指针位置可以完成交换节点，移动指针的操作
  3. cur代表每一轮待交换的指针，当在一轮交换后，我们进行指针位置修正
  4. 直到cur、next任意一方为空，结束循环

代码

ListNode* swapPairs(ListNode* head) {
    if(head == nullptr || head->next == nullptr)
        return head;

    ListNode* prev = new ListNode(0);
    ListNode* cur = head;
    ListNode* next = cur->next, *nnext = next->next;
    head = next; // 一轮交换后,head会到第二位，修正位置
    while(cur && next) // cur与next都不为空时才进行交换
    {
        // 两两交换操作
        prev->next = next;
        next->next = cur;
        cur->next = nnext;

        // 移动指针
        prev = cur;
        cur = nnext;
        next = cur ? cur->next : nullptr;
        nnext = next ? next->next : nullptr;
    }

    return head;
}

---

143.重排链表

思路

• 题目要求将链表按照规则重拍
• 我们可以按照以下思路执行（以链表[1, 2, 3, 4, 5]举例）：
  1. 将链表从中点处分开 1 2 3 与 4 5
  2. 将中点后的链表逆序 5 4
  3. 合并两链表 1 2 3 + 5 4 = 1 5 2 4 3

代码

void reorderList(ListNode* head) {
   if(!head || !head->next || !head->next->next) return;

    // 1. 找到链表中点
    ListNode* slow = head, *fast = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 2. 翻转中点后的节点
    ListNode* newhead = nullptr;
    ListNode* cur = slow->next;
    while(cur) 
    {
        ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    slow->next = nullptr; // 切断前半部分与后半部分的连接

    // 3. 合并链表（123 与 54 -> 1 5 2 4 3）
    ListNode* cur1 = head, *cur2 = newhead;
    while(cur1 && cur2) {
        ListNode* next1 = cur1->next, *next2 = cur2->next;
        cur1->next = cur2;
        cur2->next = next1;
        cur1 = next1;
        cur2 = next2;
    }
}

---

23.合并K个升序链表

思路

• 解法：小根堆
  
• 细节注意：创建小根堆时需要用自定义比较，下面我们使用自定义比较结构体、也可以使用lambda表达式

代码

class Solution {
public:
    struct cmp // 自定义比较
    {
        bool operator()(const ListNode* l1, const ListNode* l2){
            return l1->val > l2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap; // 创建小根堆

        for(auto l : lists)
            if(l) heap.push(l); // 将所有插入到堆中

        // 合并链表
        ListNode *head = new ListNode(0);
        ListNode *prev = head;
        while(!heap.empty()) // 堆有元素时，进行操作
        {
            ListNode* tmp = heap.top();
            heap.pop();

            prev->next = tmp; // 更新链表链接关系和prev
            prev = tmp;
            if(tmp->next)   heap.push(tmp->next);
        }

        prev = head->next;
        delete head;
        return prev;
    }
};

---

25.K个一组翻转链表

思路

代码

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;
        int n = 0; // 记录待翻转链表个数
        while(cur)
        {
            cur = cur->next;
            n++;
        }
        n /= k;


        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        cur = head;
        // 进行链表的分组旋转 n组 每组k个节点
        for(int i = 0; i < n; ++i)
        {
            ListNode* tmp = cur; // tmp记录每次待翻转链表的头节点
            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;
        // 删除newhead释放空间
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};