关键词：
[图]program 2019-07-24
前言
链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，链表的操作也离不开指针，指针又很容易导致出错。综合多方面的原因，链表题目在面试中占据着很重要的地位。这里总结常见的链表面试题，希望对你有所帮助！
今天的题目
1、在 O(1) 时间删除链表节点。
2、输入一个链表，输出该链表中倒数第k个结点。
3、输入一个链表，输出该链表中间的结点。
4、判断一个链表是否是回文链表。
5、从有序链表中删除重复节点。
6、删除链表的倒数第 n 个节点。
7、交换链表中的相邻结点。
8、链表元素按奇偶聚集。
9、链表求和。
10、分割链表。
1、在 O(1) 时间删除链表节点
分析：
容易想到的一个思路：用下一个节点数据覆盖要删除的节点，然后删除下一个节点。当然，在删除之前，我们需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时，时间复杂度为 O(1)。
上面的思路还有一个问题：如果删除的结点位于链表的尾部，没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺序遍历得到给定结点的前序结点，并完成删除操作。这个时候时间复杂度是 O(n)。
如果题目要求我们需要在 O(1) 时间完成删除操作，我们的算法是不是不符合要求？实际上，假设链表总共有 n 个结点，我们的算法在 n-1 总情况下时间复杂度是 O(1)，只有当给定的结点处于链表末尾的时候，时间复杂度为 O(n)。那么平均时间复杂度
[(n-1)*O(1)+O(n)]/n，仍然为 O(1)。
参考代码：
class Solution
public:
void delListNode(ListNode* pHead, ListNode* pDelNode)
if(pHead == nullptr)
return;
if(pDelNode->next == nullptr) //删除的结点位于链表的尾部
ListNode* pCur = pHead;
while(pCur->next != pDelNode)
pCur = pCur->next;
pCur->next = nullptr;
delete pDelNode;
pDelNode = nullptr;
else //用下一个节点数据覆盖要删除的节点，然后删除下一个节点
ListNode *pNext = pDelNode->next;
pDelNode->val = pNext->val;
pDelNode->next = pNext->next;
delete pNext;
pNext = nullptr;
;
2、输入一个链表，输出该链表中倒数第 k 个结点
示例1
输入
8
1 2 3 4 5 6 7 8
4
输出
5
分析：
设置两个指针，p2 指针先走（k-1）步，然后再一起走，当 p2 走到最后时，p1 就为倒数第k个数。
参考代码：
class Solution
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
if(pListHead == nullptr|| k == 0)
return nullptr;
ListNode* pTail = pListHead;
ListNode* pHead = pListHead;
for(int i=1; i<k; ++i)
if(pHead->next != nullptr)
pHead = pHead->next;
else
return nullptr;
while(pHead->next != nullptr)
pHead = pHead->next;
pTail = pTail->next;
return pTail;
;
3、输入一个链表，输出该链表中间的结点
Example 1:
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3. (The judges serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
分析：
求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。
很容易想到，如果可以求链表的长度的话，那么计算出中间节点所在链表顺序的位置即可。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法和第 2 题一样，通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。
参考代码：
class Solution
public:
ListNode *getMiddleNode(ListNode *pNode)
ListNode *fastNode = pNode;
ListNode *slowNode = pNode;
while(fastNode != nullptr && fastNode->next != nullptr)
fastNode = fastNode->next->next;
slowNode = slowNode->next;
return slowNode;
;
4、判断一个链表是否是回文链表
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
分析：依然使用两个指针，fast 和slow指针。
（1）fast 指针每次走两步，slow 指针每次走一步；
（2）fast 指针走到链表末尾的时候，slow 指针走到链表的中间位置结点（链表长度 n 为偶数）或中间位置的前一个结点（链表长度 n 为奇数）；
（3）slow 直接到了中间，就可以将整个链表的后半部分压栈实现逆序，依次和前半部分比较即可。
参考代码：
class Solution
public:
bool isPalindrome(ListNode* head)
if(head == nullptr || head->next ==nullptr)
return true;
ListNode* fast = head->next;
ListNode* slow = head;//快慢指针，让慢指针走到中间节点
while(fast != nullptr && fast->next != nullptr)
slow = slow->next;
fast = fast->next->next;
if(fast != nullptr) // 偶数节点，让 slow 指向下一个节点
slow = slow->next;
cut(head, slow); // 切成两个链表
return isEqual(head, reverseNode(slow));
private:
void cut(ListNode* head, ListNode* cutNode)
while(head->next != cutNode)
head = head->next;
head->next = nullptr;
ListNode* reverseNode(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;
bool isEqual(ListNode* L1, ListNode* L2)
while(L1 !=nullptr && L2 != nullptr)
if(L1->val != L2->val)
return false;
L1 = L1->next;
L2 = L2->next;
return true;
;
5、从有序链表中删除重复节点
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
分析：只需要在遍历时记录当前节点的前节点，然后一旦遇到有重复值的节点就跳过，直到遇到的下一个节点值和当前元素不重复；将记录的前节点的下一个元素指向和当前值不重复的节点。
参考代码：
class Solution4
public:
ListNode* deleteDuplicates(ListNode* head)
if(head == nullptr || head->next == nullptr)
return head;
ListNode* current = head;
while(current != nullptr && current->next != nullptr)
if(current->next->val == current->val) //遇到重复节点
current->next = current->next->next;
else
current = current->next;
return head;
;
6、删除链表的倒数第 n 个节点
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
分析：
这道题目要求我们一次遍历解决问题，那么就得想些比较巧妙的方法了。
比如我们首先要考虑的，如何找到倒数第 N 个节点，由于只允许一次遍历，所以我们不能用一次完整的遍历来统计链表中元素的个数，而是遍历到对应位置就应该删除了。
那么这里还是双指针的思路：首先快指针先向前走 N 步，如果此时快指向空，说明 N 为链表的长度，则需要移除的为首元素，那么此时我们返回 head->next 即可，如果快指针存在，我们再继续往下走，此时慢指针指针也跟着走，直到快指针为最后一个元素时停止，此时慢指针指向要移除元素的前一个元素，我们再修改指针跳过需要移除的元素即可。
参考代码：
class Solution
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
if(head == nullptr|| n == 0)
return nullptr;
ListNode* fast = head;
ListNode* slow = head;
while(n--)
if(fast->next != nullptr)
fast = fast->next;
else
return head->next;
while(fast->next != nullptr)
fast = fast->next;
slow = slow->next;
slow->next = slow->next->next;
return head;
;
7、交换链表中的相邻结点
Given 1->2->3->4, you should return the list as 2->1->4->3.
分析：
这道题的话，推荐读者在纸上画画，不然容易晕。细心一些就好。整个过程就是从头开始，对于每一对需要交换的节点，按顺序调整节点的 next 指针，使其指向正确的节点。
参考代码：
class Solution
public:
ListNode* swapPairs(ListNode* head)
ListNode* newHead = new ListNode(0);
newHead ->next = head;
ListNode* fast = newHead;
ListNode* slow;
while(fast->next && fast->next->next)
slow = fast->next;
fast->next = slow->next;
slow->next = slow->next->next;
fast->next->next = slow;
fast = slow;
return newHead->next;
;
8、链表元素按奇偶聚集
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
分析：处理偶链表和奇链表的指向，每隔一个元素改变指向即可。
参考代码：
class Solution
public:
ListNode* oddEvenList(ListNode* head)
if(head == nullptr || head->next == nullptr)
return head;
ListNode* odd = head;//偶链表
ListNode* even = head->next;//奇链表
ListNode* evenHead = even;//指向奇链表头节点
while(even != nullptr && even->next != nullptr)
odd->next = odd->next->next;//偶链表跳着指
odd = odd->next;
even->next = even->next->next;//奇链表跳着指
even = even->next;
odd->next = evenHead;//把偶链表接在奇链表后面
return head;
;
9、链表求和
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
分析：
题目要求：不能修改原始链表。
用容器保存每个节点 val，模拟整数相加即可
参考代码：
class Solution
public ListNode addTwoNumbers(ListNode l1, ListNode l2)
Deque<Integer> stack1 = new LinkedList<>();
Deque<Integer> stack2 = new LinkedList<>();
while (Objects.nonNull(l1))
stack1.push(l1.val);
l1 = l1.next;
while (Objects.nonNull(l2))
stack2.push(l2.val);
l2 = l2.next;
ListNode dummy = new ListNode(0);
int carry = 0;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0)
int v1 = stack1.isEmpty() ? 0 : stack1.pop();//移除并返回位于队列尾部的对象
int v2 = stack2.isEmpty() ? 0 : stack2.pop();
int sum = v1 + v2 + carry;
ListNode node = new ListNode(sum % 10);
node.next = dummy.next;
dummy.next = node;
carry = sum / 10;
return dummy.next;
;
10、分割链表
Example 1:
Input:
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \\root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].
Example 2:
Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
分析：
题目描述：把链表分隔成 k 部分，每部分的长度都应该尽可能相同，排在前面的长度应该大于等于后面的。
我们要知道每个部分结点的个数，才能将整个链表断开成子链表，所以我们首先要统计链表中结点的总个数，然后除以 k，得到的商就是能分成的部分个数，余数就是包含有多余的结点的子链表的个数。
开始 for 循环，循环的结束条件是 i 小于 k 且 root 存在，要生成 k 个子链表，在循环中，先把头结点加入结果 res 中对应的位置，然后就要遍历该子链表的结点个数了。
首先每个子链表都一定包含有 n 个结点，这是之前除法得到的商，然后还要有没有多余结点，如果 i 小于 m，就说明当前子链表还得有一个多余结点，然后将指针向后移动一位，要注意的是，这里的 j 是从 1 开始，因为要移动到子链表的最后一个结点上，而不是移动到下一个子链表的首结点。
新建一个临时结点 t 指向下一个结点，也就是下一个子链表的首结点，然后将链表断开，再将 root 指向临时结点 t，这样就完成了断开链表的操作。
参考代码：
class Solution
public:
vector<ListNode*> splitListToParts(ListNode* root, int k)
vector<ListNode*> res(k);
int len = 0;
for (ListNode* t = root; t; t = t->next) ++len;
int n = len / k, m = len % k;
for (int i = 0; i < k && root; ++i)
res[i] = root;
for (int j = 1; j < n + (i < m); ++j)
root = root->next;
ListNode* t = root->next;
root->next = nullptr;
root = t;
return res;
;
今天的分享就到这里了，希望大家能经常动手写写代码，毕竟纸上得来终觉浅，得知此事要躬行。
认真的人，自带光芒！
备战秋招冲击大厂java面试题系列—数据结构与算法(代码片段)
1.数据结构定义数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检... 查看详情
备战秋招冲击大厂java面试题系列—java集合(代码片段)
1.Collection和CollectionsCollection是集合类的上级接口，继承他的接口主要有Set和List.Collections是针对集合类的一个帮助类，他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。2.常用的集合 Collection接口... 查看详情
小c秋招面试算法题：合并k个有序数组合并k个有序链表（分治思想）(代码片段)
...链表2、合并k个有序链表后语写在前面目前大部分公司的秋招都已经结束，博主小C也在昨天10.31结束了秋招最后一场面试。最近2个月的时间，做的事情大概就是投简历、刷题、笔试、复习八股文、面试，11月到来了... 查看详情
小c秋招面试算法题：合并k个有序数组合并k个有序链表（分治思想）(代码片段)
...链表2、合并k个有序链表后语写在前面目前大部分公司的秋招都已经结束，博主小C也在昨天10.31结束了秋招最后一场面试。最近2个月的时间，做的事情大概就是投简历、刷题、笔试、复习八股文、面试，11月到来了... 查看详情
给秋招加点料——hot15道高频算法面试题！(代码片段)
目录1.链表篇反转链表判断链表中是否有环合并有序链表2.动态规划篇跳台阶子数组的最大累加和求路径最长公共子串3.树篇两个节点最近公共祖先实现二叉树先中后序排列二叉树之字形遍历4.二分篇求平方根5.其他岛屿数量最长... 查看详情
小c秋招面试算法题：合并k个有序数组合并k个有序链表（分治思想）(代码片段)
...链表2、合并k个有序链表后语写在前面目前大部分公司的秋招都已经结束，博主小C也在昨天10.31结束了秋招最后一场面试。最近2个月的时间，做的事情大概就是投简历、刷题、笔试、复习八股文、面试，11月到来了... 查看详情
服务端开发之java备战秋招面试篇2-hashmap底层原理篇(代码片段)
...，今天我们来好好整理一下这些知识，为后面的秋招做足准备，加油吧，少年。目录1、HashMap集合介绍 2、HashMap的存储过程3、HashMap的成员变量4、put()方法底层实现 5、将链表转换为红黑树 6、HashMap的扩容机制与... 查看详情
2018秋招面试题
https://blog.csdn.net/bntX2jSQfEHy7/article/details/81187626各大企业面试题：https://blog.csdn.net/huangshulang1234/article/details/79102943 一、阿里巴巴面试第一个：阿里面试都问什么？：（55分钟）011、开发中Java用了比较多的数据结构有哪些？2、... 查看详情
java秋招面试全解析：java基础+集合+多线程+mysql+redis
一眨眼就到了7月份了，2021年的秋招也马上就要来了，为了帮助广大程序员成功拿下offer，总结了一些高频面试题，以下的面经都是小编以及小编的朋友们在之前秋招的过程中被问到的一些高频问题，后面附上... 查看详情
秋招面试题系列---java工程师
前言：七月末八月初的时候，秋招正式打响，公司会放出大量的全职和实习岗位。为了帮助秋招的小伙伴们，学长这里整理了一系列的秋招面试题给大家，所以小伙伴们不用太过焦虑，相信你们一定能超常发挥，收到心仪公... 查看详情
map集合面试题
... 1.HashMap：底层基于数组+单向链表（红黑树），非线程安全，默认容量为16，允许有空的键和值 数组：Node<K,V>[]table，每一个元素都是一个Node &nbs... 查看详情
2022年java秋招面试，程序员求职必看的dubbo面试题(代码片段)
...，企业工作过的，都可参考学习!小编分享的这份2022年Java秋招备战面试题总计有1000多道面试题，包含了MyBatis、ZooKeeper、 查看详情
服务端开发之java备战秋招面试3(代码片段)
...在面试的时候有更好地表现，一起加油吧，希望秋招多拿几个令人心动的offer，冲吧。目录1、算法题：判断链表中是否有环2、算法题：合并二叉树3.什么是跳表？4.Spring的特性？5.mysql事务特性？mysql... 查看详情
[java复习02]集合框架collection-面试题小结(代码片段)
Q1Collectionjava的集合以及集合之间的继承关系?数组和链表的区别?固定长度，连续内存，不能扩展，随机访问快，插入删除慢。链表相反 List,Set,Map的区别?List，Set继承Collection接口List可以放重复数据，Set不能，Map是k-v对 List... 查看详情
秋招面试题系列---java工程师
前言：七月末八月初的时候，秋招正式打响，公司会放出大量的全职和实习岗位。为了帮助秋招的小伙伴们，学长这里整理了一系列的秋招面试题给大家，所以小伙伴们不用太过焦虑，相信你们一定能超常... 查看详情
网易2017秋招编程题集合-牛客网
网易2017秋招编程题集合-牛客网 链接：https://www.nowcoder.com/questionTerminal/0147cbd790724bc9ae0b779aaf7c5b50来源：牛客网如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：{1,2,1},{15,78,78,15... 查看详情
leetcode面试题02.06.回文链表，解题心路(代码片段)
目录leetcode面试题02.06.回文链表，解题心路1、题目描述2、java语言题解一3、java语言题解二4、C语言题解一leetcode面试题02.06.回文链表，解题心路1、题目描述编写一个函数，检查输入的链表是否是回文的。如图：试题链接：https://l... 查看详情
不要等到面试才刷面试题，160道spring高质量面试题助你征战秋招！
前言虽名为"面试题"，但一定要面试前才刷面试题嘛？其实在日常工作中多刷一些面试题对自己也是挺有帮助的！为此小编收集了160道Spring中高级面试题给大家学习，查漏补缺！ 另外小编还收集了一些Sp... 查看详情