[Algorithm][链表][两数相加][两两交换链表中的节点][重排链表][合并K个升序链表][K个一组翻转链表] + 链表原理 详细讲解

0.常用技巧

• 画图 -> 直观 + 形象 -> 便于理解

• 引入虚拟头结点

  • 便于处理边界情况
  • 方便对链表操作

• 不要吝啬空间，大胆去定义变量

  • 简化插入删除的逻辑
  • 都是函数内的临时变量，也不会很占用空间:P
    

• 快慢双指针

  • 判环
  • 找链表中环的入口
  • 找链表中倒数第n个结点

1.两数相加

1.题目链接

• 两数相加

2.算法原理详解

• 两个链表都是逆序存储数字的
  • 即：两个链表的个位数、⼗位数等都已经对应，可以直接相加
• 在相加过程中，要注意是否产⽣进位，产⽣进位时需要将进位和链表数字⼀同相加
  • 如果产⽣进位的位置在链表尾部，即答案位数⽐原链表位数⻓⼀位，还需要再new⼀个结点储存最⾼位

3.代码实现

ListNode* AddTwoNumbers(ListNode* l1, ListNode* l2) 
{
    ListNode* head = new ListNode(0);
    ListNode* cur1 = l1, *cur2 = l2;
    ListNode* tail = head; // 尾指针

    int carry = 0; // 记录进位 & 临时数据
    while(cur1 || cur2 || carry)
    {
        if(cur1)
        {
            carry += cur1->val;
            cur1 = cur1->next;
        }

        if(cur2)
        {
            carry += cur2->val;
            cur2 = cur2->next;
        }

        tail->next = new ListNode(carry % 10);
        tail = tail->next;

        carry /= 10;
    }

    ListNode* ret = head->next;
    delete head;

    return ret;
}

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

1.题目链接

• 两两交换链表中的节点

2.算法原理详解

3.代码实现

ListNode* SwapPairs(ListNode* list) 
{
    // 边界处理
    if(list == nullptr || list->next == nullptr)
    {
        return list;
    }

    ListNode *head = new ListNode(0);
    head->next = list;

    ListNode *prev = head, *cur = head->next, *next = cur->next, *nNext = next->next;

    while(cur && next)
    {
        // Swap
        prev->next = next;
        next->next = cur;
        cur->next = nNext;

        // Update
        prev = cur;
        cur = nNext; 
        if(cur)
        {
            next = cur->next;
        }
        if(next)
        {
            nNext = next->next;
        }
    }

    ListNode *ret = head->next;
    delete head;

    return ret;
}

3.重排链表

1.题目链接

• 重排链表

2.算法原理详解

• 找到链表的中间结点
  • 快慢双指针
• 把后面部分逆序
  • 头插法
• 合并两个链表
  • 双指针
    

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 *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;
    }

    // 3.合并两个链表 -> 尾插 -> 双指针
    ListNode *ret = new ListNode(0);
    ListNode *tail = ret;
    ListNode *cur1 = head, *cur2 = head2->next;
    while(cur1)
    {
        // 先连第一个链表
        tail->next = cur1;
        tail = tail->next;
        cur1 = cur1->next;

        // 再连第二个链表
        if(cur2)
        {
            tail->next = cur2;
            tail = tail->next;
            cur2 = cur2->next;
        }
    }

    delete head2;
    delete ret;
}

4.合并 K 个升序链表

1.题目链接

• 合并 K 个升序链表

2.算法原理详解

• 思路一：利用堆
  • 合并K个升序链表时，可以选择K个链表中，头结点值最⼩的那⼀个
  • 那么如何快速的得到头结点最⼩的是哪⼀个呢？
    • 小根堆
  • 可以把所有的头结点放进⼀个⼩根堆中，这样就能快速的找到每次K个链表中，最⼩的元素是哪个
• 思路二：递归/分治
  

3.代码实现

// v1.0 Heap
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& list : lists)
        {
            if(list)
            {
                heap.push(list);
            }
        }

        // 合并K个有序链表
        ListNode* ret = new ListNode(0);
        ListNode* tail = ret;
        while(!heap.empty())
        {
            ListNode* tmp = heap.top();
            heap.pop();

            tail->next = tmp;
            tail = tail->next;

            if(tmp->next)
            {
                heap.push(tmp->next);
            }
        }

        tail = ret->next;
        delete ret;

        return tail;
    }
};

// v2.0 递归
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 mid = left + (right - left) / 2;
        // [left, mid] [mid + 1, right]

        // 递归处理左右区间
        ListNode* l1 = Merge(lists, left, mid);
        ListNode* l2 = Merge(lists, mid + 1, right);

        // 合并两个有序链表
        return MergeTwoLists(l1, l2);
    }

    ListNode* MergeTwoLists(ListNode* l1, ListNode* l2)
    {
        // 边界情况处理
        if(l1 == nullptr)
        {
            return l2;
        }

        if(l2 == nullptr)
        {
            return l1;
        }

        // 合并两有序链表
        ListNode head(0);
        ListNode *cur1 = l1, *cur2 = l2, *tail = &head;
        while(cur1 && cur2)
        {
            if(cur1->val <= cur2->val)
            {
                tail->next = cur1;
                tail = tail->next;

                cur1 = cur1->next;
                
            }
            else
            {
                tail->next = cur2;
                tail = tail->next;

                cur2 = cur2->next;
            }
        }

        if(cur1)
        {
            tail->next = cur1;
        }

        if(cur2)
        {
            tail->next = cur2;
        }

        return head.next;
    }
};

5.K 个一组翻转链表

1.题目链接

• K 个一组翻转链表

2.算法原理详解

• 思路：
  • 按k个一组，分出需要逆序多少组
    • 遍历链表求出n
    • n /= 3
  • 重复n次，长度为k的链表逆序即可

3.代码实现

ListNode* ReverseKGroup(ListNode* head, int k) 
{
    // 遍历求n
    int n = 0;
    ListNode* cur = head;
    while(cur)
    {
        n++;
        cur = cur->next;
    }
    n /= k;

    // 重复n次逆序长度为k的链表 -> 头插
    ListNode ret(0);
    ListNode *prev = &ret;
    cur = head;
    while(n--)
    {
        ListNode *back = cur;
        for(int i = 0; i < k; i++)
        {
            ListNode* next = cur->next;
            cur->next = prev->next;
            prev->next = cur;
            cur = next;
        }
        prev = back; // 更次每次头插的"头"
    }

    // 链接剩下的结点
    prev->next = cur;

    return ret.next;
}