本文首发于微信公众号：聊点技术，原文标题《 面试腾讯时遇到了"链表"的原题，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){ //相交返回trueList* 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); //返回环的入口点，无环则返回nullptrList* enter2 = ListCrossEnterNode(head2);if (enter1 == nullptr && enter2 == nullptr){ //两链表无环if (EnterNode(head1, head2)){return true;}elsereturn 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;}elsecout << "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
好了，面试过程中常见的和链表有关的题目在文中基本都列出来了。一起努力，相信大家都能够找到自己满意的工作！欢迎大家关注 “聊点技术”，我会陆续将我的秋招经验进行总结并发布到公众号上。