你好，我是安然无虞。

大家好, 好久不见了, 从今天开始, 后面会经常更新笔试面试真题, 准备今年24届秋招的小伙伴可以提前看过来了哦.

咱们先从链表入手, 基础知识默认大家都会咯, 直接热题开刷, 走着…

我们知道单链表题型中有许多技巧, 其中有很多题都属于那种难者不会, 会者不难的题型, 满满的套路感, 下面整理了九道题目, 基本对应了七种技巧, 面试常考题型, 一起看看吧.

合并两个有序链表

题目链接: 合并两个有序链表
题目描述:

解题思路:

这道题就比较简单了, 属于单链表入门题型, 但是如果要让解法更简单, 最好定义一个虚拟头结点, 结果直接返回其next即可.

代码详解:

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {// 定义一个虚拟头结点ListNode* newnode = new ListNode(-1), *p = newnode;ListNode* p1 = list1, *p2 = list2;// p1和p2均不为空时while(p1 && p2){if(p1->val < p2->val){p->next = p1;p1 = p1->next;}else{p->next = p2;p2 = p2->next;}p = p->next;}// p1不为空if(p1)p->next = p1;// p2不为空if(p2)p->next = p2;return newnode->next;    }
};

---

分隔链表

题目链接: 分隔链表
题目描述:

解题思路:

前面一题我们是将两条有序链表合并成一条有序链表, 这一题可以将原链表分割成为两条链表.
也就是说将原链表分割成为节点值小于x的短链表和节点值不小于x的短链表即可.

注意:
如果看代码不明白的话, 最好画图去理解.

代码详解:

class Solution {
public:ListNode* partition(ListNode* head, int x) {// 定义两个虚拟头结点// 分成节点值小于x的短链表和节点值不小于x的短链表ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;// 遍历比较原链表while(head != nullptr){if(head->val < x){p1->next = head;p1 = p1->next;}else{p2->next = head;p2 = p2->next;}head = head->next;}// 将节点值不小于x的短链表的尾置空p2->next = nullptr;p1->next = newnode2->next;return newnode1->next;}
};

---

合并K个有序链表

题目链接:合并K个有序链表
题目描述:

解题思路:

前面有讲到合并两个有序链表, 其实合并K个有序链表和它的解题思想很类似, 但是为了能够快速获取K个链表的最小节点, 我们需要定义一个最小堆, 将K个链表的头结点插入其中, 这样一来, 每次就可以获取K个节点的最小节点.

代码解析:

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {// 定义一个虚拟头结点, 将所有节点尾插其后ListNode* newnode = new ListNode(-1), *p = newnode;// 定义一个最小堆, 将K个链表的头结点插入其中// 用到了C++中新语法, 不熟悉的小伙伴可以去查阅哦priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});for(auto head : lists){if(head != nullptr)pq.push(head);}while(!pq.empty()){// 获取堆顶节点, 即当前最小节点, 尾插到新链表后ListNode* pMin = pq.top();pq.pop();p->next = pMin;// if(pMin->next != nullptr)pq.push(pMin->next);p = p->next;}return newnode->next;}
};

---

链表中倒数最后K个节点

题目链接: 链表中倒数最后K个节点
题目描述:

解题思路:

本题是想找到链表的最后K个节点, 前提是要找到倒数第K个节点, 如何在一次遍历的情况下找到呢?
首先定义两个指针p1和p2, 均指向链表的头结点. 一开始让p1先走k步(此时如果p1再走n-k步就走到链表的尾了), 这个时候p2从头和p1一起走, 直到p1指向nullptr为止, 此时p2在第n-k+1个节点上, 即倒数第k个位置, 大家可以画图去理解, 这里我就不画了哈哈哈哈.

代码详解:

class Solution {
public:ListNode* FindKthToTail(ListNode* pHead, int k) {// write code hereListNode* p1 = pHead, *p2 = pHead;if(pHead == nullptr)return nullptr;// p1先走k步for(int i = 0; i < k; i++){// 注意判断防止越界导致段错误if(p1)p1 = p1->next;elsereturn nullptr;}// p2从头开始和p1一起走, 直至p1指向nullptr时, p2所在位置即为倒数第k个位置while(p1 != nullptr){p1 = p1->next;p2 = p2->next;}return p2;}
};

变形题: 删除链表的倒数第N个节点

题目链接: 删除链表的倒数第N个节点
题目描述:

解题思路:

单链表中删除某一个节点, 前提是要先找到该节点的前一个节点, 同时为了防止头删第一个节点, 我们还需要定义一个虚拟头结点, 将head节点尾插其后.

代码解析:

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {// 定义一个虚拟头结点 - 注意单链表对虚拟头结点的运用ListNode* newnode = new ListNode(-1);newnode->next = head; // 防止头删第一个节点// 单链表中删除某一个节点, 前提需要找到它前一个节点ListNode* prev = findFromEnd(newnode, n + 1);prev->next = prev->next->next;return newnode->next;}// 单链表中找倒数第K个节点ListNode* findFromEnd(ListNode* head, int k){// 定义两个指针p1和p2, p1先走k步(再走n-k步到尾), 然后p2从头开始h和p1一起走// 直到p1指向空, 此时p2在第n-k+1个节点的位置, 即倒数第k个节点ListNode* p1 = head, *p2 = head;if(head == nullptr)return nullptr;for(int i = 0; i < k; i++){if(p1)p1 = p1->next;elsereturn nullptr;}while(p1){p1 = p1->next;p2 = p2->next;}return p2;}
};

---

链表的中点

题目链接: 链表的中点
题目描述:

解题思路:

利用快慢指针, 快指针一次走两步, 慢指针一次走一步, 当快指针指向末尾时, 慢指针所在的位置即是链表的中点.

代码详解:

class Solution {
public:ListNode* middleNode(ListNode* head) {// 定义快慢指针ListNode* slow = head;ListNode* fast = head;// 快指针一次走两步, 慢指针一次走一步// 当快指针指向末尾时, 慢指针即是中点// 画图更好理解while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}
};

---

判断链表是否有环

题目链接: 判断链表是否有环
题目描述:

解题思路:

利用快慢指针, 很简单不说了

代码详解:

class Solution {
public:ListNode* middleNode(ListNode* head) {// 定义快慢指针ListNode* slow = head;ListNode* fast = head;// 快指针一次走两步, 慢指针一次走一步// 当快指针指向末尾时, 慢指针即是中点// 画图更好理解while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}
};

---

环形链表II

题目链接: 环形链表II
题目描述:

解题思路:

下面是我两年前画的图…大家可以参考

代码解析:

class Solution {
public:ListNode *detectCycle(ListNode *head) {// 定义快慢指针ListNode* slow = head;ListNode* fast = head;// 判断链表是否有环while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast)break;}    // 循环非break退出, 说明没环if(fast == nullptr || fast->next == nullptr)return nullptr;// 否则有环, slow从头重新开始走// 二者再次相遇即为入口点slow = head;while(slow != fast){slow = slow->next;fast = fast->next;}return slow;}
};

---

相交链表

题目链接: 相交链表
题目描述:

解题思路:

这题的解题思路就比较有意思了, 本题是求相交链表的交点, 难点在于什么, 就像上图一样, 链表A和链表B的长度很大可能不一样, 这样我们就做不到一次循环可以找到二者的交点, 那如何解决该难点呢?
我们可以定义两个指针p1和p2, 其中p1指向链表A, p2指向链表B. 一开始p1先遍历链表A然后再遍历链表B, 同理p2先遍历链表B再遍历链表A, 这样就可以保证二者遍历长度相同, 能够同时走到相交点.

代码分析:

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 定义两个指针, p1指向链表A, p2指向链表BListNode* p1 = headA;ListNode* p2 = headB;// 为了让p1和p2遍历链表的长度一样, 采用下面的做法while(p1 != p2){// p1遍历完链表A, 开始遍历链表Bif(p1 == nullptr)p1 = headB;elsep1 = p1->next;// p2遍历完链表B, 开始遍历链表Aif(p2 == nullptr)p2 = headA;elsep2 = p2->next;}// 交点返回即可 - 画图去理解return p1;}
};

---

种一棵树最好的时间是十年前, 其次是现在.

一起加油, 我们很快就会再见.