链表面试常见考题（C++实现）

常用方法：画图法

常用技巧：用于遍历搜索的游标 ListNode* cur; 用于返回值的哑节点 ListNode* dumny = new ,,

单链表更新先去考虑他的next指向问题。链表元素或者边界问题可以用前继节点pre、后继节点tail来进行判断。

1: 从尾到头打印单链表

解题思路：

从尾到头，利用栈先进后出的原理，使用栈数据结构遍历存放单链表的数据，之后出栈。

class Solution {
public:vector<int> reversePrint(ListNode* head) {/* 根据返回值定义存储结果的变量 */vector<int> result;/* 因为要反向输出值所以先把数据放入栈立里面然后在拿出来 */stack<int> st;ListNode* cur = head;/* 将数据压入栈 */while(cur != NULL) {st.push(cur->val); // 单链表数据元素入栈cur = cur->next;}/* 将栈中的数据弹出 利用栈的性质可以反向输出结果 */while(!st.empty()) {result.push_back(st.top()); //将栈顶元素存放st.pop(); // 弹出栈顶元素}return result;}
};

2: 单链表实现约瑟夫环

约瑟夫环问题： 围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

思路：利用单链表数据结构，每次找到目标节点，之后将该节点从链表移除。更新当前的头节点，再次遍历寻找目标节点，之后剩下一个节点为止。

class solution
{
public:ListNode* YSF(ListNode* head, int m){if (head == NULL) {return NULL;}ListNode* cur = NULL; // 游标while (head->next != head) { // 保证遍历到最后只剩一个最新的头节点for (int i = 0; i < m - 1; i++) {cur = head; // cur最后指向的是目标节点的前一个节点head = head->next; // head最后移动到了目标节点} cur->next = head->next; // 目标节点从链表移除DeleteListNode(head); // 删除head = cur->next; // 头节点重新指向下一轮的第一个节点（cur->next就是）}return head;}void DeleteListNode(ListNode* node){if (node == NULL) {return;}node->val = 0;node->next = NULL;free(node);node == NULL;}
};

3: 逆置/反转单链表

反转链表： 1 2 3 4 5  反转到 5 4 3 2 1。

思路： 单链表的反转，需要一个临时存储节点，用来记录反转前的链表指针指向的节点。否则反转完就不知道next是什么。同时需要一个新的pre节点告诉当前节点的前一个节点。最后返回最新的头结点。

class solution
{
public:ListNode* reverseNode(ListNode* head){ListNode* tmp; // 定义一个存储节点，存放反转前的后继节点ListNode* cur = head; // 游标ListNode* pre; // 定义一个前继节点while(cur) {tmp = cur->next; // 存储后继节点cur->next = pre; // 反转pre = cur; // 前继节点更新cur = tmp; // 游标移动到下一个节点   }return pre; // pre最后指向了最新的头节点}};

4: K个节点一组进行翻转

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

思路： 和第3题不同的是这个需要找到前继节点(pre)和后继节点(tail),之后在按照第3题进行类似的反转操作。本题目主要是移动后继结点实现反转。

class Solution
{
public:ListNode* reverseBetween(struct ListNode* head, int left, int right){if (head == NULL) {return NULL; }ListNode* cur = head; // 定义一个游标ListNode* pre = NULL; // 定义一个前继节点ListNode* tail = NULL; // 定义一个后继节点int gap = right - left + 1; //int i = 0;while(cur) {i++;// 1: find preif (left >= 1 && i = left - 1) {pre = cur; // 当I移动到left的前一个，就找到了pre}// 2: find tailif (i > = left) {gap--; }if (gap == 0) {tail = cur->next; break;}// 3: 没找到tail,继续移动游标 curcur = cur->next;}// start reversecur = head;ListNode* tmp = NUll;int I = 0;gap = right - left + 1; // 反转的次数// 尾指针法while(cur) {i++;if (i >= left && gap > 0) {gap--;tmp = cur->next; // 存放后继节点cur->next = tail; // 反转，当前节点指向尾节点tail = cur; // 尾指针移动if (gap == 0) {break; // 完成反转} else {cur = tmp; // 移动游标，反转下一个节点 continue;}}cur = cur->next;}if (left != 1) { // pre->next = cur;return head;}return cur;}};

5：单链表排序

链表 4 2 1 3 实现排序， 时间复杂度O(nlogn)， 空间复杂度O(1)

思路：利用归并排序， 自顶向下的排序。

归并排序： （1）找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2步，慢指针每次移动 1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中间节点。

                   （2）根据中间递归拆分链表为子链表（最后拆分为最小单位，只有1个节点，头节点的next为tail）

                   （3）将拆分好的子链表 （两两合并），合并子链表时候，先判断小的节点，依靠游标将他们串联起来。

class Solution {
public:ListNode* sortList(ListNode* head) {return SortList(head, nullptr);}ListNode* SortList(ListNode* head, ListNode* tail){if (head == nullptr) {return nullptr;}if (head->next == tail) {head->next = nullptr;return head; // 只有一个节点， 返回本身就可以}ListNode* slow = head;  // 慢指针ListNode* fast = head;  // 快指针ListNode* mid =  nullptr;  // 中间节点while (fast != tail) { // 这里要注意，fast不能超出范围，保证块的，慢的就可以保证slow = slow->next;fast = fast->next;if (fast != tail) {fast = fast->next; // 快指针移动两步}}mid = slow;return MergeList(SortList(head, mid), SortList(mid, tail)); // 递归去拆分寻找子链表的中间节点}ListNode* MergeList(ListNode* head1, ListNode* head2)  // 入参为两个要合并的子链表的头节点{ListNode* dumyNode = new ListNode(1);ListNode* cur = dumyNode;ListNode* tmp1 = head1;ListNode* tmp2 = head2;while (tmp1 && tmp2) {if (tmp1->val <= tmp2->val) {cur->next = tmp1;tmp1 = tmp1->next;} else {cur->next = tmp2;tmp2 = tmp2->next;}cur = cur->next;} // 看谁还有剩余元素if (tmp1 != nullptr) {cur->next = tmp1;} else if (tmp2 != nullptr) {cur->next = tmp2;}cur = cur->next;cur->next = nullptr;return dumyNode->next;}};

6： 寻找单链表的中间节点

思路： 只遍历一次的话，使用快慢指针。快指针每次移动 2步，慢指针每次移动 1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中间节点。不管是奇数偶数都可以。

class Solution
{public：ListNode* FindMidNode(ListNode* head){if (head == nullptr) {return nullptr;}ListNode* tail = nullptr;if (head->next == tail) {head->next = nullptr;return head;}ListNode* slow = head;ListNode* fast = head;while (fast != tail) {slow = slow->next;fast = fast->next;if (fast != tail) {fast = fast->next;}}ListNode* mid = slow;return mid;}};

7: 删除列表中倒数第K个节点 （一次遍历）

思路： 快慢指针

（1）快慢指针同时指向头节点

（2）快指针比慢指针先领先k步，之后再一起移动

（3）快慢指针一起移动，每次移动一步，当快指针超出链表，那么领先了k步，因此慢指针指向的链表节点就是倒数第K个节点。

class Solution {
public:ListNode* getKthFromEnd(ListNode* head, int k) {if (head == nullptr || k == 0) {return nullptr;} ListNode* fast = head;ListNode* slow = head;int i = 0;while (i < k) {fast = fast->next;i++;if (i == k && fast == nullptr) {return slow;} else if (fast == nullptr) {return nullptr;}}ListNode* tail = nullptr;while (fast != tail) {fast = fast->next;slow = slow->next;}return slow;}
};

8：删除链表倒数第k个节点

思路： 先用快慢指针找到倒数第k个节点。找的时候定义一个指向目标节点的前继节点，用于后续的删除操作。（查找方法将题7）

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if (head == nullptr) {return NULL;}ListNode* slow = head;ListNode* fast = head;ListNode* pre = nullptr; // // 快速节点向前移动k步int i = 0;while (i < n) {fast = fast->next;i++;if (i == n && fast == nullptr) {return slow->next;} else if (fast == nullptr) {return slow;}}// 快慢指针移动寻找到倒数第k个节点 (slow锁指向的节点)ListNode* tail = nullptr;while (fast != tail) {pre = slow;slow = slow->next;fast = fast->next;}pre->next = slow->next;return head;}
};

9：判断链表是否带环？若带环，求环的长度？和入口点？

思路： 快慢指针，快指针比慢指针多走两步。当两者相遇说明有环。

class Solution {
public:bool hasCycle(ListNode *head) {if (head == NULL) {return false;}// 快慢指针ListNode* slow = head;ListNode* fast = head;ListNode* tail = nullptr;while(fast != tail) {slow = slow->next;fast = fast->next;if (fast != tail) {fast = fast->next; // 快指针移动两步} else {return false;}// 如果相遇则说明有环if (fast == slow) {return true;}}return false;}
};

求解环的入口点：

思路：继续使用快慢指针，当快慢指针相遇的时候，快指针永远是慢指针的2倍。

a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

块指针走了：a+(n+1)b+nc。 

慢指针走了： a+b 

class Solution {
public:ListNode *detectCycle(ListNode *head) {if (head == nullptr) {return nullptr;}ListNode* slow = head;ListNode* fast = head;// ListNode* pre = head;ListNode* tail = nullptr;while (fast != tail) {slow = slow->next;fast = fast->next;if (fast != tail) {fast = fast->next;} else {return nullptr;}if (slow == fast) {while (pre != slow) {pre = pre->next;slow = slow->next;}return pre;}}return nullptr;}};

10： 合并两有序链表

思路： 创建一个哑节点，不断循环比较，让哑节点去指向两者小的一方，并且小的一方移动。

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {// 哑节点游标法，不需要创建新的节点ListNode* dunmy = new ListNode(-1); // 题目中没有head节点，需要我们自己创建一个哑节点ListNode* cur = dunmy; // 创建一个游标指向当前的哑节点// 遍历寻找while (l1 && l2) { // &&关系if  (l1->val < l2->val) {cur->next = l1; // 游标的指向l1 = l1->next;} else {cur->next = l2; // 游标的指向l2 = l2->next;}cur = cur->next; // 移动游标}// 寻找最后的剩余if (l1) {cur->next = l1;// 游标的指向} else {cur->next = l2;// 游标的指向}cur = cur->next;// 移动游标return dunmy->next;}
};

11： 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

思路： 先遍历整个链表，找到最后一个节点，并统计整个链表长度。

之后求出偏移（取余），找到旋转后的尾节点。修改链表头和尾的指向。

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (head == nullptr) return nullptr;if (k == 0) return head;// 计算链表长度, cur指向链表尾节点 ListNode *cur = head;int listLen = 0;while (cur->next) {cur = cur->next;listLen++;}listLen++;// 计算旋转分割节点int goStep = listLen - (k % listLen);// 求出新的尾节点ListNode *tail = head;int i = 1;while (i < goStep && tail) {tail = tail->next;i++;}// 进行旋转if (tail->next == nullptr) {return head;}ListNode* res = tail->next;tail->next = NULL;cur->next = head;return res;}
};