面试腾讯时遇到了“链表“的原题，so easy！

本文首发于微信公众号：聊点技术，原文标题《 面试腾讯时遇到了"链表"的原题，so easy！》 找工作的过程中，不论是参加笔试还是面试，我们都会遇到大量和链表有关的题目。我在找实习的时候，经历的第一场面试是腾讯的电话面试，两道编程题目中有一道就是本文中提到的：复杂链表的复制。秋招期间，在经历了多次笔试和面试后，我把曾经遇到过的与链表有关的题目进行了分类总结，总结成此文期待能够对各位朋友有所帮助。

本文总结了在面试中遇到频率最高的与链表有关的题目，并使用了C++进行编码实现。

链表节点定义如下：

struct List{ int val; struct List* next; List(int x) : val(x), next(nullptr){} };

1.从尾到头打印单链表

非递归算法：利用两个指针，指针cur指向链表尾部，指针tail指向链表头部。每当tail从头循环到尾部cur时，输出表尾的值。让表尾cur指向tail，再次循环。

void PrintTailToHead(List* head){ //非递归O(n^2) List* cur = nullptr; while(cur != head){ List* tail = head; //重新指向头节点 while(tail->next != cur){ //循环移动到尾 tail = tail->next; } cout<< tail->val << endl; cur = tail; //更新尾节点 } } void TailToHead(List* head){ //递归算法 O(n) if(head == nullptr){ return ; } TailToHead(head->next); cout<< head->val << endl; }

2. 删除单链表的节点

a. 删除给定单链表中的节点

若要删除的链表节点非尾 若要删除的节点位于链表的尾部，那么它就没有下一个节点——需要从链表头节点开始，顺序遍历得到该节点的前序节点，并完成删除操作 如果链表中只有一个节点，又要删除链表的头节点，那么在删除节点后，需要把链表头节点置空

void DeleteNode(List** head, List* pos){ if(head == nullptr || pos == nullptr){ return; } if(pos->next != nullptr){ /*要删除节点不是尾节点，采用向前替换法*/ List* next = nullptr; next = pos->next; pos->val = next->val; pos->next = next->next; delete next; next = nullptr; } else if (*head == pos){ /* pos->next为空跳过第一个if. 在第二个if内判断 */ delete pos; /* pos->next为空，且pos和*head相同，此时只有一个节点*/ pos = nullptr; *head= nullptr; /* 使用指向指针的指针的原因 */ } else{ /* pos->next为空，且pos!=*head。此时要删除尾节点*/ List* p = *head; while(p->next != pos){ p = p->next; } p->next = nullptr; delete pos; pos = nullptr; } }

b. 简化版：删除一个无头单链表的非尾节点。

//采用向前替换法

void ListDelNode(List* pos){ List* cur = nullptr; cur = pos->next; pos->val = cur->val; pos->next = cur->next; free(cur); cur = nullptr; }

c. 删除排序链表中的重复节点

从头遍历整个链表。如果当前节点的值与下一个节点的值相同，那么他们就是重复的节点，都可以被删除。为了保证被删除之后的链表仍然是相连的，要把当前节点的前一个节点（pPreNode）和后面值比当前节点的值大的节点相连。

void DeleteDuplication(ListNode** pHead){ //头结点也可能被删除，因此采用指向指针的指针 if (pHead == nullptr || *pHead == nullptr) return; ListNode* pPreNode = nullptr; ListNode* pNode = *pHead; while (pNode != nullptr){ ListNode* pNext = pNode->next; bool needDelete = false; if (pNext != nullptr && pNext->val == pNode->val){ //next节点不为空且当前节点和next节点值相等 needDelete = true; //说明他们就是重复节点，都可以被删除 } if (!needDelete){ //不是重复节点。指针后移 pPreNode = pNode; pNode = pNode->next; } else{ //遇到重复节点 int value = pNode->val; //保存值，因后边会删除该节点 ListNode* ToBeDel = pNode; while (ToBeDel != nullptr && ToBeDel->val == value){ //直至遇到值不等节点 pNext = ToBeDel->next; delete ToBeDel; ToBeDel = pNext; } if (pPreNode == nullptr){ //说明是开头几个节点被删除。 *pHead = pNext; } else{ pPreNode->next = pNext; //当前节点的前驱指向后继。 } pNode = pNext; //当前指针后移 } } }

3. 无头单链表节点前插入节点

void InsertNode(List* pos, int x){ //1.创建一个新节点保存pos节点的数据。 //2.将pos节点的值改为新插入的值。 //3.将新创建的节点插入到pos节点后。 List* cur = new List(pos->val); cur->next = pos->next; pos->next = cur; pos->val = x; }

4.反转单链表

List* ReverseList(List* head){ //头插法 if (head == nullptr) return nullptr; List* pHead = new List(-1); //创建一个作为头节点 List* p = head; //第一个节点 while (p != nullptr){ List* q = p->next; //保存下一个节点 p->next = pHead->next; //插入到头部 pHead->next = p; p = q; } return pHead->next; }

5. 合并有序链表

List* MergeSortedList(List* head1, List* head2){ if (head1 == nullptr) return head2; if (head2 == nullptr) return head1; List* pHead = new List(-1); //合并后新链表的头节点 List* prev = pHead; while (head1 != nullptr && head2 != nullptr){ if (head1->val < head2->val){ prev->next = head1; head1 = head1->next; } else{ prev->next = head2; head2 = head2->next; } prev = prev->next; } if (head1 != nullptr){ prev->next = head1; } if (head2 != nullptr){ prev->next = head2; } return pHead->next; }

6.查找单链表的中间节点

快慢指针法：建立两个指针slow和fast，初始时两个指针都指向单链表的头结点。依次向后移动，fast指针的移动速度是slow指针的2倍。当fast指向末尾节点的时候，slow就正好在正中间。

List* FindMidNode(List* head){ //只能遍历一次链表 if (head == nullptr) return head; List* slow = head; List* fast = head; while(fast != nullptr && fast->next != nullptr){ slow = slow->next; fast = fast->next->next; //循环判断条件中fast和fast->next都不为空才可执行. //因此此处不需要判断fast->next是否为空 /*********************************** fast = fast->next; if(fast != nullptr) fast = fast->next; ***********************************/ } return slow; }

7. 查找单链表的倒数第k个节点

分析：假设有节点1、2、3、4、5、6。倒数第3个节点是值为4的节点。假设整个链表有n个节点，倒数第k个节点就是从头节点开始的第n-k+1个节点。 定义两个指针：第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历；由于两个指针的距离保持在k-1.当第一个指针到达链表的尾节点时，第二个指针正好指向倒数第k个节点。

List* FindTailKthNode_1(List* head, int k){ //要求只能遍历一次链表 if (head == nullptr || k <= 0) return head; List* slow = head; List* fast = head; for (int i = 0; i < k-1; ++i){ //fast指针先走k-1步 if (fast->next == nullptr){ return nullptr; //节点数少于k } else{ fast = fast->next; } } while (fast->next){ //当fast->next为空. slow指向倒数第K个节点 slow = slow->next; fast = fast->next; } return slow; } List* FindTailKthNode(List* head, int k){ if (head == nullptr || k <= 0) return head; List* slow = head; List* fast = head; for (int i = 0; i < k; ++i){ if (fast->next == nullptr){ return nullptr; } else{ fast = fast->next; } } while (fast){ //当fast==nullptr，slow指向倒数第K个节点 slow = slow->next; fast = fast->next; } return slow; }

8. 带环链表操作

a. 判断两个无环链表是否相交

bool ListCross(List* head1, List* head2){ if (head1 == nullptr || head2 == nullptr) return false; while (head1 && head1->next){ head1 = head1->next; } while (head2 && head2->next){ head2 = head2->next; } //分别遍历两个链表，若两链表最后一个结点相同即相交 if (head1 == head2 && head1 != nullptr) return true; return false; }

b. 两个链表相交，求交点

List* EnterNode(List* head1, List* head2){ if (head1 == nullptr || head2 == nullptr) return nullptr; bool IsCross = ListCross(head1, head2); //首先判断是否相交 if (IsCross){ //相交返回true List* cur1 = head1; List* cur2 = head2; int len1 = 0; int len2 = 0; while (cur1){ //前两个while统计两链表长度 ++len1; cur1 = cur1->next; } while (cur2){ ++len2; cur2 = cur2->next; } cur1 = head1; cur2 = head2; int d = len1 - len2; //长度差值 if (d < 0){ //需要找出较长的链表。cur1指向较长的链表，cur2指向较短的链表。 cur1 = head2; cur2 = head1; d = len2 - len1; } while (d--){ //长的链表先走。让较长的链表从头走它们的长度差值。 cur1 = cur1->next; } while (cur1 != cur2){ //两个一起向后走，相遇即相交，且相遇点即为交点 cur1 = cur1->next; cur2 = cur2->next; } return cur1; } return nullptr; }

c 判断是否有环，有环返回相遇结点

List* IsCycleList(List* head){ if (head == nullptr) return nullptr; List* slow = head; List* fast = head; while (fast != nullptr && fast->next != nullptr){ if (slow == fast){ return slow; } slow = slow->next; fast = fast->next->next; } return nullptr; }

d. 环的入口点

List* ListCrossEnterNode(List* head){ if (head == nullptr) return nullptr; List* meetNode = IsCycleList(head); if (meetNode == nullptr) return nullptr; List* p = head; while (p != meetNode){ p = p->next; meetNode = meetNode->next; } return p; }

e. 判断两个有环链表是否相交

两个链表都不带环—直接进行常规判断—调用EnterNode（两链表相交，求交点函数）； 一个带环，一个不带环—不可能相交； 两个均带环：在环外相交，则入口点相同；在环内相交，则从一个链表的入口点环绕一周即可找到另一链表的入口。

bool ListCrossWithCycle(List* head1, List* head2){ if (head1 == nullptr || head2 == nullptr) return false; List* enter1 = ListCrossEnterNode(head1); //返回环的入口点，无环则返回nullptr List* enter2 = ListCrossEnterNode(head2); if (enter1 == nullptr && enter2 == nullptr){ //两链表无环 if (EnterNode(head1, head2)){ return true; } else return false; } if (enter1 == nullptr || enter2 == nullptr) //一个带环，一个不带环——不可能相交 return false; if (enter1 == enter2){ //两个都有环且入口点相同——在环外相交 return true; } List* cur = enter1->next; //两个都带环，但入口点不同——在环内相交 while (cur != enter1){ if (cur == enter2) // 从一个链表的入口点环绕一周即可找到另一链表的入口。 return true; cur = cur->next; } return false; //两个都带环，但不相交 }

f. 复制一个可能有环的单向链表

List* CopyList(List* head){ unordered_map<List*, List*> m; if (head == NULL) return NULL; List* cur = head; List* newHead = new List(-1); //复制的链表的头节点 List* copyP = newHead; // 1.当无环时，会有cur == NULL跳出while循环 // 2.当有环时，不会有cur == NULL. 但是会存在m[cur] != 0的情况跳出循环 // m[cur]中存放的是下一个节点的指针。 while (cur != nullptr && m[cur] == 0){ //cur指向不为空且hash表里没有当前已保存的地址 List* tmp = new List(cur->val); //创建新的节点 copyP->next = tmp; m[cur] = tmp; cur = cur->next; } if (m[cur] != 0) //m[cur]不等于0说明遇到了环 copyP->next = m[cur]; return newHead->next; }

g. 求环的长度

int ListLength(List* head){ if (head == nullptr) return -1; List* meetNode = IsCycleList(head); if (meetNode == nullptr) return -1; int n = 1; List* cur = meetNode; while (cur->next != meetNode){ ++n; cur = cur->next; } return n; }

h. 在实际笔试的时候，可以灵活应用。如，2019年携程笔试中有一道题目是关于有环链表的判断。

样例1： 输入格式：a,b,c,d,a 输出格式：true 样例2： 输入格式：a,b,c,d 输出格式：false 这个题目可以自己根据输入创建一个链表，然后再进行判断。但是比较复杂，可以采用下面的思路：针对输入数组的最后一个元素，在前面的数据中查找，如果查找到，说明存在环。

int IsCyc(){ vector<int> data; char temp; while (cin >> temp){ if (temp == ',') continue; data.push_back(temp); } char c = data[data.size()-1]; auto p = find(data.begin(), data.end() - 1, c); if (p != (data.end() - 1)){ cout << "true" << endl; } else cout << "false" << endl; return 0; }

9. 旋转单链表多字段排序

给定一个链表，旋转链表，使得每个结点向后移动k个位置，其中k是非负数。 例. 输入：1->2->3->4->5->NULL k=2 返回：4->5->1->2->3->NULL 解析：找到倒数第k个位置结点，将其变为头结点。

ListNode* rotateList(ListNode* head, int k){ int start = 0; ListNode* fast = head; while (start < k && fast->next != nullptr){ fast = fast->next; ++start; } if (fast->next == nullptr || start < k){ /*循环结束后，若start<k表示k比整个链表还要长。旋转后还是单链表*/ return head; /*如果fast->next==nullptr表示n正好等于原链表的长度，此时不需要旋转*/ } ListNode* pre = fast; /*倒数第k+1个结点*/ ListNode* newHead = fast->next; /*倒数第k个结点。旋转后的头结点*/ while (fast->next != nullptr){ /*fast指针走到链尾*/ fast = fast->next; } fast->next = head; /*原链表的最后一个结点指向原来的头结点*/ pre->next = nullptr; /*原链表的倒数第k+1个结点变为尾节点*/ return newHead; }

10. 复杂链表的复制

在复杂链表中，每个节点除了有一个next指针指向下一个节点外，还有一个random指针指向链表中的任意节点或nullptr. 复制过程分为三个步骤： 根据原始链表中的每个节点N创建对应的N’. 把N’链接在N的后面。 设置复制出来的节点的random指针。 把长链表拆分成两个链表。

struct ListNode{ int val; struct ListNode* next; struct ListNode* random; ListNode(int x = -1) :val(x), next(nullptr), random(nullptr){} }; void CloneNodes(ListNode* head){ //复杂链表的复制步骤1. //1.根据原始链表中的每个节点N创建对应的N'. 把N'链接在N的后面。 ListNode* cur = head; while (cur != nullptr){ ListNode* pNode = new ListNode(); pNode->val = cur->val; pNode->next = cur->next; pNode->random = nullptr; cur->next = pNode; cur = pNode->next; } } void ConnectRandomPtr(ListNode* head){ //复杂链表的复制步骤2. //2.设置复制出来的节点的random指针。假设原始链表上的N节点的 //random指针指向节点S.那么其对应复制出来的N'是N的next指向的节点， //同样S'也是S的next指向的节点。 ListNode* cur = head; while (cur != nullptr){ ListNode* pNode = cur->next; if (cur->random != nullptr){ pNode->random = cur->random->next; } cur = pNode->next; } } ListNode* ReconnectNode(ListNode* head){ //复杂链表的复制步骤3. //3.把这个长链表拆分成两个链表：把奇数位置的节点用next链接起来 //就是原始链表，把偶数位置的节点用next链接起来就是复制出来的链表。 ListNode* pNode = head; ListNode* pClonedHead = nullptr; ListNode* pClonedNode = nullptr; if (pNode != nullptr){ pClonedHead = pClonedNode = pNode->next; pNode->next = pClonedNode->next; //将偶数位的第一个节点拆分出来 pNode = pNode->next; //奇数位的指针后移 } while (pNode != nullptr){ pClonedNode->next = pNode->next; pClonedNode = pClonedNode->next; pNode->next = pClonedNode->next; pNode = pNode->next; } return pClonedHead; } ListNode* Clone(ListNode* head){ //合并上述三个步骤。 CloneNodes(head); ConnectRandomPtr(head); return ReconnectNode(head); }

11.单链表冒泡排序

void BubbleSort(List* head){ if (head == nullptr) return; if (head->next == nullptr) return; List* cou = head; List* tail = nullptr; for (cou = head; cou != nullptr; cou = cou->next){ List* cur = head; for (; cur->next != tail; cur = cur->next){ if (cur->val > cur->next->val){ swap(cur->val, cur->next->val); } } tail = cur; //一轮结束后最后一个为最大值，下一轮比较时少更新一个。 } }

12. 链表分组反转

给定一个链表，每次按照K个为一组进行翻转操作，并返回修改后的链表。如果节点数不是K的倍数，那么剩余的结点就保持原样。 输入格式：[1,2,3,4,5] 2 输出格式：[2,1,4,3,5] 本题是Leetcode第25题，标注级别为Hard。

ListNode* CreateLinkList(vector<int> &vec) { if (vec.empty()) return nullptr; ListNode *head = new ListNode(vec.back()); head->next = nullptr; for (int i = vec.size() - 2; i >= 0; --i) { ListNode *newNode = new ListNode(vec[i]); newNode->next = head; head = newNode; } return head; } void PrintLinkList(ListNode* head) { ListNode* node = head; cout << "["; while (node != nullptr) { std::cout << node->val; if (node->next != nullptr) cout << ","; node = node->next; } cout << "]" << endl; return; } //链表每次按照K个一组进行翻转 ListNode* ReverseKGroup(ListNode* head, int k) { ListNode* headNode = new ListNode(0); ListNode* cur = head; ListNode* p = headNode; //初始时p指向头结点 headNode->next = head; int num = 0; while (cur){ //计数。统计一共多少个节点 ++num; cur = cur->next; } while (num >= k) { //若长度小于分组长度则不旋转 int n = k; cur = p->next; while (--n) { ListNode *tmp = cur->next; cur->next = tmp->next; tmp->next = p->next; p->next = tmp; } p = cur; num -= k; } p = headNode->next; delete headNode; return p; } void Input(vector<int>& vec) { char c; int tmp; string str; getline(cin, str); //一次性按照字符串个数读入一行 istringstream record(str); //将读入的字符串绑定到流istringstream上 while (record >> tmp >> c) { vec.push_back(tmp); } } int ReversrMain() { int k; vector<int> vec; Input(vec); ListNode* head = CreateLinkList(vec); cin >> k; ListNode* newHead = ReverseKGroup(head, k); PrintLinkList(newHead); system("pause"); return 0; }

THE END 好了，面试过程中常见的和链表有关的题目在文中基本都列出来了。一起努力，相信大家都能够找到自己满意的工作！欢迎大家关注 “聊点技术”，我会陆续将我的秋招经验进行总结并发布到公众号上。