面试高频算法-链表
01 认识『链表』
链表的结构十分简单，其本身是一种线性的存储结构，通过物理地址不连续的节点相连接成链。最简单的单链表只包含一条链，并且每一个节点包括两部分内容，数据元素和下一个节点的地址。因此可通过已知节点访问它的下一个节点。
相比于数组而言，由于链表不必须按顺序存储，因而在插入的时候可以达到O(1)的复杂度，一般而言比数组的效率要高得多；但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而数组由于可以直接通过下标寻址，相应的时间复杂度仅为O(1)。
一般可通过定义结构体的方式来实现链表：
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
02 高频算法题
1. 输入一个链表，输出该链表中倒数第k个结点。
快慢指针的方法在链表相关的操作中经常使用。
通过设置快慢指针，快指针先前进k步，之后快慢指针同时前进，此时快慢指针间隔k步；当快指针到达链表尾部，此时慢指针所在节点即为倒数第k个节点。这样的方法仅通过一次遍历即可获得倒数第k个节点。
代码如下：
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(pListHead==NULL||k==0)
return NULL;
ListNode*pTail=pListHead,*pHead=pListHead;
for(int i=1;i<k;++i)
{
if(pHead->next!=NULL)
pHead=pHead->next;
else
return NULL;
}
while(pHead->next!=NULL)
{
pHead=pHead->next;
pTail=pTail->next;
}
return pTail;
}
};
2. 输入一个链表，反转链表后，输出新链表的表头。
非递归方法的解题思路需要理解以下四步，具体见下图：
代码如下：
//第一种方法：非递归方法 /*
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead==NULL)
return NULL;
ListNode* cur = pHead;
ListNode* pre = NULL;
ListNode* head = NULL;
while(cur != NULL)
{
if(cur->next==NULL)
head = cur;
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return head;
}
};
//第二种方法是：递归方法 /*
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
//如果链表为空或者链表中只有一个元素
if(pHead==NULL||pHead->next==NULL) return pHead;
//先反转后面的链表，走到链表的末端结点
ListNode* pReverseNode=ReverseList(pHead->next);
//再将当前节点设置为后面节点的后续节点
pHead->next->next=pHead;
pHead->next=NULL;
return pReverseNode;
}
};
3. 将两个有序链表合并为一个新的有序链表并返回。
这题可通过设置双指针的方式对链表不同节点元素进行筛选：
代码如下：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
};4. 寻找两个相交链表的公共起点。
这题同样可以设置快慢指针，比较常规的方法可以先求得2个链表的长度，然后让长链表指针先前进两个链表的长度差，然后再一起前进；最后当快慢指针相遇的位置即是公共起点。
代码如下：
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 != NULL){
if(pHead1 == pHead2) return pHead1;
pHead1 = pHead1->next;
pHead2 = pHead2->next;
}
return NULL;
}
int findListLenth(ListNode *pHead1){
if(pHead1 == NULL) return 0;
int sum = 1;
while(pHead1 = pHead1->next) sum++;
return sum;
}
ListNode* walkStep(ListNode *pHead1, int step){
while(step--){
pHead1 = pHead1->next;
}
return pHead1;
}
};5. 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
这题同样可采用快慢指针的方法来做。
快指针每次前进2步，慢指针每次前进1步。若链表有环，则快慢指针会在环内相遇。假设图中b是环的入口，a为链表起点，c为快慢指针相遇的位置。由于快慢指针的前进时间相同，则根据速度关系可得：
2(ab+bc)=ab+bc+cb+bc，则得ab=bc
所以当快慢指针相遇后，从相遇点到环入口的距离与从链表头到环入口的距离一样。通过设置一指针从链表头部前进，一指针从相遇点同时前进，两指针相遇的位置即是链表环的入口。
代码如下：
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode*fast=pHead,*low=pHead;
while(fast&&fast->next){
fast=fast->next->next;
low=low->next;
if(fast==low)
break;
}
if(!fast||!fast->next)
return NULL;
low=pHead;//low从链表头出发
while(fast!=low){//fast从相遇点出发
fast=fast->next;
low=low->next;
}
return low;
}
};03 总结
链表相关的算法在面试中经常考察，其考察的重点在于对链表结构熟练的操作，包括指针的切换、节点的增删和变形等等。
上面所举的几个例子都是对链表比较基本的处理，可以从中理解到链表常用的快慢指针、遍历以及边界判断等问题。
另外，面试中出现的链表相关的高频算法题目可参考以下Leetcode题号：
Leetcode 19 删除链表的倒数第N个节点
Leetcode 21 合并两个有序链表
Leetcode 23 合并K个排序链表
Leetcode 25 K个一组翻转链表
Leetcode 86 分隔链表
Leetcode 109 有序链表转换二叉树
Leetcode 138 复制带随机指针的链表
Leetcode 141 环形链表
Leetcode 160 相交链表
Leetcode 206 反转链表
ps：关注公众号业余码农，回复【链表】可获得更多链表相关算法的完整代码，都是面试考察重点！
拼多多集团-PDD公司氛围 535人发布
查看7道真题和解析