秋招之路-链表面试题集合（一）

本文主要是介绍秋招之路-链表面试题集合（一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[图]program 2019-07-22

这是 herongwei 的第 79 篇原创

阅读本文大概需要 6.66 分钟

前言

链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，链表的操作也离不开指针，指针又很容易导致出错。综合多方面的原因，链表题目在面试中占据着很重要的地位。这里总结常见的链表面试题，希望对你有所帮助！

今天的题目

1、单链表翻转

2、输入两个单链表，找出它们的第一个公共结点

3、归并有序的两个链表（递归和非递归）

1、定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而线性表和顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。

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

2、单链表翻转

参考代码：

/*//当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点//需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2//即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了//所以需要用到pre和next两个节点//1->2->3->4->5//1<-2<-3 4->5//1.做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre//如此就可以做到反转链表的效果//先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂//2.保存完next，就可以让head从指向next变成指向pre了//3.head指向pre后，就继续依次反转下一个节点//4.让pre，head，next依次向后移动一个节点，继续下一次的指针反转
*/
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {ListNode* pReversedHead = nullptr;ListNode* pCur = pHead;ListNode* pPre = nullptr;while(pCur != nullptr) {ListNode* pNext = pCur->next;//链断开之前一定要保存断开位置后边的结点if(pNext == nullptr) //当next为空时，说明当前结点为尾节点pReversedHead = pCur;pCur->next = pPre;pPre = pCur;pCur = pNext;}return pReversedHead;}
};//栈存储
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {std::stack<int> st;ListNode* p = pHead;ListNode* q = pHead;while (p) {st.push(p->val);p = p->next;}while (q) {q->val = st.top();st.pop();q = q->next;}return pHead;}
};

3、输入两个单链表，找出它们的第一个公共结点

参考代码

/*
一般两种思路
思路一：找出 2 个链表的长度，然后让长的先走两个链表的长度差，然后再一起走（因为 2 个链表用公共的尾部）
思路二：不用计算长度：
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
如果不存在交点，那么 a + b = b + a，以下实现代码中 l1 和 l2 会同时为 null，从而退出循环。
*/class Solution {
public:ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {int len1 = findListLenth(pHead1);int len2 = findListLenth(pHead2);if(len1 > len2){pHead1 = walkStep(pHead1,len1 - len2);}else{pHead2 = walkStep(pHead2,len2 - len1);}while(pHead1 != nullptr){if(pHead1 == pHead2) return pHead1;pHead1 = pHead1->next;pHead2 = pHead2->next;}return nullptr;}int findListLenth(ListNode *pHead){if(pHead == nullptr) return 0;int sum = 1;while(pHead = pHead->next) sum++;return sum;}ListNode* walkStep(ListNode *pHead, int step){while(step--){pHead = pHead->next;}return pHead;}
};class Solution {
public:ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {ListNode *p1 = pHead1;ListNode *p2 = pHead2;while(p1!=p2){p1 = (p1==nullptr ? pHead2 : p1->next);p2 = (p2==nullptr ? pHead1 : p2->next);}return p1;}
};

如果只是判断是否存在交点，那么就是另一个问题，即编程之美 3.6 的问题。有两种解法：

1、把第一个链表的结尾连接到第二个链表的开头，看第二个链表是否存在环；

2、或者直接比较两个链表的最后一个节点是否相同。

4、归并两个有序的链表

思路类似归并排序。

参考代码

//1、递归
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == nullptr) return l2;if (l2 == nullptr) return l1;if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};
//2、非递归
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){ListNode * head = new ListNode(0);ListNode * tmp = head;while(l1 != nullptr && l2 != nullptr) {if(l1->val < l2->val) {tmp->next = l1;l1 = l1->next;} else {tmp->next = l2;l2 = l2->next;}tmp = tmp->next;}if(l1 != nullptr) tmp->next = l1;if(l2 != nullptr) tmp->next = l2;return head->next;//pointer to the start of tmp is returned}
};

如果觉得写得不错，欢迎点好看，转发哦~