笔者投的是嵌入式软件岗，发现手撕代码难度上比软件开发岗是要简单一些的，基本都是leetcode的medeium和easy的水平，基本难的算法不会考，集中在字符串处理和链表，现在把一些常见的链表题做一下。(以下题目均用c++，在类函数里实现)
1.leetcode 21 合并两个有序链表
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
这个题有两种算法，一种是常规算法，一种是递归算法，后者写出来感觉牛逼一点，但是容易出错。
方法一：
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode() : val(0), next(nullptr) {}
*ListNode(int x) : val(x), next(nullptr) {}
*ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy=new ListNode(0);
//虚拟头结点不动
ListNode *cur=dummy;
//这个结点是变化的
if(l1==nullptr)
return l2;
if(l2==nullptr)
return l1;
while(l1!=nullptr&&l2!=nullptr)
{
if(l1->valval)
{
cur->next=l1;
l1=l1->next;
}
else
{
cur->next=l2;
l2=l2->next;
}cur=cur->next;
}if(l1!=nullptr)
cur->next=l1;
else
cur->next=l2;
return dummy->next;
}
};
方法2：递归算法
终止条件：当两个链表都为空时，表示我们对链表已合并完成。
如何递归：判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
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);
//较小结点的next指向其余结点
return l1;
}
else
{
l2->next=mergeTwoLists(l1,l2->next);
return l2;
}}
};
2、leetcode 23 合并k个升序链表
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
提示：优先级队列（二叉堆） 这种数据结构，把链表节点放入一个最小堆，就可以每次获得
k 个节点中的最小节点【手撕|应对嵌入式校招面试手撕之——链表】首先搞一个笨方法，两两合并，借助上边的代码。
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode() : val(0), next(nullptr) {}
*ListNode(int x) : val(x), next(nullptr) {}
*ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy=new ListNode(0);
//虚拟头结点不动
ListNode *cur=dummy;
//这个结点是变化的
if(l1==nullptr)
return l2;
if(l2==nullptr)
return l1;
while(l1!=nullptr&&l2!=nullptr)
{
if(l1->valval)
{
cur->next=l1;
l1=l1->next;
}
else
{
cur->next=l2;
l2=l2->next;
}cur=cur->next;
}if(l1!=nullptr)
cur->next=l1;
else
cur->next=l2;
return dummy->next;
}
ListNode* mergeKLists(vector& lists) {
if(lists.size()==0)
return nullptr;
ListNode* head = lists[0];
for (int i = 1;
i < lists.size();
++i) {
head = mergeTwoLists(head, lists[i]);
}
return head;
}
};
就是循环一遍，这个方法太蠢了，要搞一个优先级队列来解决这些问题。初始化，我投进去k个有序列表的头结点，优先级判断一遍，取最小的接到dummy上，每投一个把这个结点的下一个结点放入优先级队列，得到新理论的最小接到dummy上，知道当前结点的下一个结点不存在。
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode() : val(0), next(nullptr) {}
*ListNode(int x) : val(x), next(nullptr) {}
*ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
struct cmp{
bool operator()(const ListNode *a,const ListNode *b)
{
return a->val>b->val;
//这里从大到小，队列的头是最大的，队列的尾是最小的,取走一个b,b->next补充
}
};
class Solution {
public:
ListNode* mergeKLists(vector& lists) {
if(lists.size()==0) return nullptr;
priority_queue,cmp> pq;
for(auto list:lists){
if(list)
pq.push(list);
//初始化，先把头入队，现在自动排序了
}ListNode *dummy=new ListNode(0);
ListNode *cur=dummy;
while(!pq.empty())
{
cur->next=pq.top();
pq.pop();
cur=cur->next;
if(cur->next!=nullptr)
{
pq.push(cur->next);
}
}
return dummy->next;
}
};
141、环形链表（快慢指针，注意边界条件，fast->next->next已经运行一次了，fast->next就是下一个结点，结合循环理解一下，肯定是快指针先到边界）
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==nullptr) //注意：结点为空判断一下
return false;
ListNode *fast=head;
ListNode *slow=head;
while(fast&&fast->next)//注意判断条件，一定是fast先碰到尾部
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
return true;
}
return false;
}
};
142、环形链表2 这个题主要是找到环之后找环的起点，和一个数学公式有关，这里当环相遇的时候，把其中一个结点放在环的起始点，然后每次前进一步，再次相遇，就找到了起点。
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {ListNode *fast=head;
ListNode *slow=head;
while(fast&&fast->next)//注意判断条件，一定是fast先碰到尾部
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
ListNode *tmp1=slow;
while(tmp1!=head)
{
tmp1=tmp1->next;
head=head->next;
}
return head;
}
}
return nullptr;
//注意，没找到返回空}
};
876、链表的中间结点
思路：快慢指针，当fasy走道链表末尾时，slow就指向了终点。
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode() : val(0), next(nullptr) {}
*ListNode(int x) : val(x), next(nullptr) {}
*ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *fast=head;
ListNode *slow=head;
if(head==nullptr)
return nullptr;
while(fast!=nullptr&&fast->next!=nullptr)
{
slow=slow->next;
fast=fast->next->next;
//快指针跳出循环时，慢指针到终点}
return slow;
}
};
160、相交链表
给你两个单链表的头节点
headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。思路：解决这个问题的关键是，通过某些方式，让
p1 和 p2 能够同时到达相交节点 c1。我们可以让
p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。如果这样进行拼接，就可以让
p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：（这个思路秒啊）/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1=headA;
ListNode *p2=headB;
while(p1!=p2)
{
if(p1==nullptr)
p1=headB;
//直接让它等于另一个的头结点
else
p1=p1->next;
if(p2==nullptr)
p2=headA;
else
p2=p2->next;
}
return p1;
}
};
19、删除链表的第N个结点。
给你一个链表，删除链表的倒数第
n 个结点，并且返回链表的头结点。最好一次遍历实现
首先，我们先让一个指针
p1 指向链表的头节点 head，然后走 k 步：现在的
p1，只要再走 n - k 步，就能走到链表末尾的空指针用一个指针
p2 指向链表头节点 head，正好走n-k步就可以了。/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode() : val(0), next(nullptr) {}
*ListNode(int x) : val(x), next(nullptr) {}
*ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* findFromEnd(ListNode *head,int n)
{
ListNode *p1=head;
ListNode *p2=head;
for(int i=0;
inext;
}
while(p1!=nullptr)
{
p2=p2->next;
p1=p1->next;
}
return p2;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *dummy=new ListNode(0);
dummy->next=head;
//虚拟节点，防止只有一个节点，删了之后就没有了
ListNode *tmp=findFromEnd(dummy,n+1);
//这里是虚拟节点，防止tmp->next->next不存在,找到倒数的n+1个，然后删去
tmp->next=tmp->next->next;
return dummy->next;
}
};
注意细节，当出现p->next->next时，一定想一想p->next不能时nullptr。
接下来会有一个链表专题练习，练个20道。
推荐阅读
- 数据结构|LeetCode每日一刷 --- 手撕单链表习题（1）
- 算法|软件工程师 算法工程师_采访100多位软件工程师后的建议
- python|硬件工程师需要数学功底吗_您不需要数学就可以成为软件工程师
- 面试系列|阿里面试官偷偷给我的软件测试工程师面试题，拿offer率老高了
- java|JVM性能调优~JVM内存整理及GC回收
- 算法|排序算法和二分查找
- COMS 4771 分析
- 《LeetCode算法全集》|LeetCode 146. LRU 缓存
- 蓝桥真题|【蓝桥真题六】三十块的蓝桥省赛模拟真题，做的大一都直呼上当（文末PDF原题）