[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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

---

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

---

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34