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