链表编程题题解

写在前面

链表的题基本都可以转化为数组，去操作，但是这篇博客没有这种操作，我更建议去体会链表自身的奇妙操作。

反转链表

原题链接：反转链表
这道题我们需要反转给定的链表，这里用的是递归的方法，原因是代码简单。
我们可以把递归想象成一个黑河测试（C++开发方向的我表示没学，但是不影响）假设递归函数是dfs() 那我们只需要想清楚其中的一次操作，剩下的就交给dfs() 慢慢做就好了。如果你想反驳说，这不就是dp吗，但是dp问题本身就可以用dfs()暴力解决（不在乎时间复杂度的情况下，如果你是剪枝高手当我没说）。但是dp却不能解决所有dfs()问题。
由于命名规范问题，为了达到统一，前一个节点为pre，当前节点为cur；
这里我们的一次操作仅仅是把cur的下一个节点cur->next指向当前节点cur,然后把当前节点的指针置空就好。

代码实现：

		//由于需要两个节点，所以先判空
       if(!head || !head->next) return head;
       //由于我们操作的下一个节点指向当前节点，所以我们的方向就是从后往前
       ListNode* newHead = ReverseList(head);
       //开始操作
       head->next->next = head;
       head->next = nullptr;
       //返回头节点，此时的头节点已经是原来的尾节点
       return newHead;
1
2
3
4
5
6
7
8
9

链表内指定区间反转

原题链接： 链表内指定区间反转

这里由于我们只需要翻转一个区间，所以我们只需要找到这个区间的头和尾然后把这个区间取出来，翻转结束再放回去就可以，这个取和放的过程就是力扣上的穿针引线方法，但是牛客网这里是用的迭代，所以我们也来迭代。
有一个问题要注意，就是我们用这种迭代的时候，由于他不是递归，我们要注意要new一个新的头节点。这个新的头节点的作用就是找原头节点，为了不让读者困惑，我来详细说一下，就是如果你的翻转是第一个节点和第二个节点，因为这种翻转方式他在翻转cur和cur->next的时候需要一个pre来接住cur->next，这个新的头就是为了这种情况。

代码实现：

	ListNode* reverseBetween(ListNode* head, int left, int right) {
        //申请新头
        ListNode* newHead = new ListNode(-1);
        newHead->next = head;
        //pre 和 cur 的初始化
        ListNode* pre = newHead;
        ListNode* cur = newHead->next;
        int now = 1;
        //找到需要翻转的区间的头
        for(int i = 1; i < left; i++) pre = cur, cur = cur->next;
        //开始翻转
        for(int i = left; i < right; i++) {
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp;
        }
        //这里一定要想着释放之前申请的头，如果这个不是编程，而是一个项目，这里就内存泄漏了
        ListNode* ans = newHead->next;
        delete(newHead);
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

链表中的节点每k个一组翻转

原题链接：链表中的节点每k个一组翻转
这个就是多反转了几组。套上面就行。
由于他是多反转一次，所以这个递归味太重了，直接递归，递归的话就不需要考虑申请头节点了，参考第一个就可以很快写出代码。

代码实现：

	ListNode* reverseKGroup(ListNode* head, int k) {
		//前一个节点，当前节点的初始化
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* tail = head;
        //要是不够K个就不需要翻转，如果是就找到为需要翻转区间的头节点和尾节点，这里的头节点正好就是上次翻转结束的节点
        for(int i = 0; i < k; i++) 
            if(tail == nullptr) return head;
            else tail = tail->next; 
        //找到之后开始翻转，这里和第一题不同的是，如果这里是不同的组，必须要有组内的关联，否则就会每个组都少最后一个
        for(int i = 0; i < k; i++) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            
            pre = cur;
            cur = tmp;
        } 
        head->next = reverseKGroup(tail, k);
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

合并两个排序的链表

原题链接：合并两个排序的链表
那就是那个小选那个就可以，所以要判断很多次，又是重复子问题，直接递归。

代码实现：

	ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //如果有一个是空，直接返回另一个
        if(!pHead1) return pHead2;
        if(!pHead2) return pHead1;
        //谁小选谁
        if(pHead1->val <= pHead2->val) {
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        }
        else {
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

合并k个已排序的链表

原题链接：合并k个已排序的链表
如果有人是把他都放到一个数组然后用sort我个人认为这种代码比较丑陋。
所以这里我们用堆来实现（小根堆），用优先队列实现小根堆，这里的优先队列的第三个参数是CLASS类型的所以这里如果是用匿名函数的话要用decltype关键字修饰一下，C++14的时候decltype才开始支持auto。

代码实现：

	ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode * a, ListNode * b) {
            return a->val > b->val;
        };
        //用STL直接建立小根堆
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        //把数据都放入堆
        for(int i = 0; i < lists.size(); i++) {
            if(lists[i]) pq.push(lists[i]);
        }
        //由于没给原头，直接申请一个头
        ListNode* newHead = new ListNode(-1);
        ListNode* head = newHead;
        //按照顺序对堆的每一个都进行链接
        while(pq.size()) {
            ListNode* tmp = pq.top();
            pq.pop();
            head->next = tmp;
            head = head->next;
            if(tmp->next) pq.push(tmp->next);
        }
        //记录答案
        ListNode* ans = newHead->next;
        //释放掉原先申请的头
        delete newHead;
        return ans;
    }
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

判断链表中是否有环

原题链接：判断链表中是否有环
这里通过快慢指针来走每一个点，如果快慢指针相遇那么就是有环

代码实现：

	bool hasCycle(ListNode *head) {
        //如果链表本身就没有那就没有环
        if(!head) return false;
        //初始化快慢指针
        ListNode* fast = head;
        ListNode* lower = head;
        while(fast && fast->next) {
            fast = fast->next->next;
            lower = lower->next;
            //快慢指针相遇就是有环
            if(lower == fast) return true;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

链表中环的入口结点

原题链接： 链表中环的入口结点

• 我们假设 a为出发点到环入口长度，b为环长度
• fast速度是slow 的两倍，当相遇时，设走过的路径长度为：slow = s ，fast = s +
  nb，即fast比slow多走了n圈环
• 因为时间相同，fast速度为slow两倍，路径自然是slow的两倍，因此：2s = s + nb, 即 s = nb，
• 因为速度不同，肯定能相遇，所以当第一次相遇时，slow走了nb步，fast走了2nb
• 相遇后，让 fast重新从出发点按slow指针相同速度走 因为此时 slow 已经走了 nb 的路程，fast走了2nb路程
• 而正常情况走到环入口，最少需要走: a + b，目前slow走了nb步了，需要再走a步就能从相遇点走到环入口节点
• 而当fast是从起点重新走到入口节点，刚好也是路程 a，刚好再次相遇，也就是刚好走到入口节点 总的路程：slow = a + nb，
  fast = a + 2nb，刚好满足在入口节点相遇的路程

很重要的一点：指针在走的过程中，从起点走到环里后，会一直在环里转圈

代码实现：

```cpp
	//判断是否有环
    ListNode* hasCycle(ListNode* head) {
        if(!head) return nullptr;
        ListNode* fast = head;
        ListNode* lower = head;
        while(fast && fast->next) {
            fast = fast->next->next;
            lower = lower->next;
            if(lower == fast) return lower;
        }
        return nullptr;
    }
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* lower = hasCycle(pHead);
        //如果没环就不可能有入口节点
        if(!lower) return nullptr;
        ListNode* fast = pHead;
        while(fast != lower) {
            fast = fast->next;
            lower = lower->next;
        }
        return lower;
    }
};
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

链表中倒数最后k个结点

原题链接：链表中倒数最后k个结点
我们只需要用双指针维护一个大小为K的区间，然后让R指针走到最后即可。

代码实现：

	ListNode* FindKthToTail(ListNode* pHead, int k) {
        if(!pHead) return nullptr;
        ListNode* r = pHead;
        ListNode* l = pHead;
        for(int i = 0; i < k; i++) {
            if(r) r = r->next;
            else return nullptr;
        }
        while(r) {
            r = r->next;
            l = l->next;
        }
        return l;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

删除链表的倒数第n个节点

原题链接： 删除链表的倒数第n个节点
我们只需要维护一个大小为n的滑动窗口，就可以找到倒数第n个节点，然后把节点的前一个指向后一个就可以完成删除操作。

代码实现：

	ListNode* removeNthFromEnd(ListNode* head, int n) {
        //由于可能删除第一个节点，所以我们预留出一个新节点
        ListNode* newHead = new ListNode(-1);
        newHead->next = head;
        //双指针维护一个大小为n的滑动窗口，这里的是l - r 之间的节点数是n
        ListNode* r = head;
        ListNode* l = newHead;
        while(n--) r = r->next;
        while(r) {
            r = r->next;
            l = l->next;
        }
        //最后的l->next就是要删除的节点
        ListNode* cmp = l->next;
        l->next = l->next->next;
        //一定要注意，被删除的节点要释放掉，不然就内存泄漏了
        delete cmp;
        //释放内存
        ListNode* ans = newHead->next;
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

两个链表的第一个公共结点

原题链接：两个链表的第一个公共结点
因为他们有公共的节点，所以我们只需要让两个链表到达公共节点的距离是一样的就可以了，所以我们只需把第一个链表在结尾加上第二个链表，把第二个链表在结尾加上第一个链表，他们第一个相同的点就是第一个公共节点。

代码实现：

	ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		//分别找到两个的头
        ListNode* list1 = pHead1;
        ListNode* list2 = pHead2;
        //如果不相等就往后找
        while(list1 != list2) {
            list1 = list1 ? list1->next : list2;
            list2 = list2 ? list2->next : list1;
        }
        return list1;
    }
1
2
3
4
5
6
7
8
9
10
11

链表相加(二)

原题链接：链表相加(二)
我们可以先把链表翻转之后再相加，之后再翻转，但是这里有一个小问题就是这里的数据个数是1e6如果我们在这里使用递归的话，就是爆内存，具体为什么其实我也没太懂，我超时是合理的，爆内存确实有点离谱，但是我们就可以直接一次模拟过去。

代码实现：

	ListNode* reverseList(ListNode* head) {
        if(!head) return nullptr;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp; 
        }
        return pre;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
    	//如果其中一个是空，那么相加得到的结果就是另一个链表
        if(!head1) return head2;
        if(!head2) return head1;
        //分别翻转两个链表
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        //这里我们要创建一个新的链表来记录相加的结果，所以我们申请一个新头，其实找一个原链表直接操作也行，但是就修改了原链表，不利于程序的健壮性。
        ListNode* newHead = new ListNode(-1);
        ListNode* head = newHead;
        //记录进位
        int flag = 0;
        while(head1 || head2 || flag) {
            int val1 = head1 == nullptr ? 0 : head1->val;
            int val2 = head2 == nullptr ? 0 : head2->val;
            //进位计算
            int tmp = val1 + val2 + flag;
            flag = tmp / 10;
            tmp %= 10;
            //把得到的节点放到新的链表，由于新的链表没有空闲内存，所以我们每次都需要自己申请
            head->next = new ListNode(tmp);
            head = head->next;
            if(head1) head1 = head1->next;
            if(head2) head2 = head2->next;
        }
       	//释放内存
        ListNode* ans = newHead->next;
        delete newHead;
        //最后把结果链表再翻转回来
        return reverseList(ans);
    }
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