目录
引言
这次的题均来自力扣和牛客有关链表的经典面试题,代码只会展示最优的解法,之前发布过单链表的经典算法--单链表经典算法-CSDN博客,大家可以先看看经典算法,再看这个面试题,会轻松很多,如果觉得这篇博客对你有帮助的话,一定要点赞关注哦!
面试题01:返回倒数第k个节点
--面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）
题目描述:
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2 输出： 4说明：
给定的 k 保证是有效的。
思路分析:
这道题最快的解题方法为快慢指针,大家可以先去看单链表经典算法-CSDN博客中的链表的中间节点.也就是定义两个指针,快指针先走k步,再让快慢指针同时走,直到快指针为NULL,两个指针之间恒定相差为k步,最后的慢指针即为倒数第k个节点.如下图所示:
代码展示:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int kthToLast(struct ListNode* head, int k){
struct ListNode* fast = head, *slow = head;
//快指针先走k步
while(k--)
{
fast = fast->next;
}
//同时走
while(fast)
{
fast = fast->next;
slow = slow->next;
}
return slow->val;
}面试题02:链表的回文结构
--链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
题目描述:
描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1 返回：true
思路分析:
这道题主要难在它的空间复杂度要求为O(1),也就是不能在创建新的链表,所以重点从如何判断回文结构入手,我们不难发现,找到链表的中间节点,再将链表另一侧翻转,如果两边相同即为回文结构,如下图所示:
这里就涉及了两个算法,一个是找到链表的中间节点并返回,一个是翻转链表.这两个算法大家可以去看单链表经典算法-CSDN博客,哪里我详细讲解了这两个算法的实现,这里我就不多说了,直接给出代码:
代码展示:
找到链表的中间节点
struct ListNode* middleNode(struct ListNode* head) {
//创建快慢指针
ListNode*slow = head;
ListNode*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}翻转链表
struct ListNode* reverseList(struct ListNode* head) {
//判空
if(head == NULL)
{
return head;
}
//创建三个指针
ListNode*n1,*n2,*n3;
n1 = NULL,n2=head,n3=n2->next;
while(n2)
{
n2->next = n1;
n1=n2;
n2=n3;
//n2没走完时,n3已经为空,要进行判空
if(n3)
n3 = n3->next;
}
return n1;
}完整代码:
class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head) {
//判空
if(head == NULL)
{
return head;
}
//创建三个指针
ListNode*n1,*n2,*n3;
n1 = NULL,n2=head,n3=n2->next;
while(n2)
{
n2->next = n1;
n1=n2;
n2=n3;
//n2没走完时,n3已经为空,要进行判空
if(n3)
n3 = n3->next;
}
return n1;
}
struct ListNode* middleNode(struct ListNode* head) {
//创建快慢指针
ListNode*slow = head;
ListNode*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool chkPalindrome(ListNode* A) {
// write code here
struct ListNode* mid = middleNode(A);
struct ListNode* rmid = reverseList(mid);
while(rmid && A)
{
if(rmid->val != A->val)
return false;
rmid = rmid->next;
A = A->next;
}
return true;
}
};面试题03:相交链表
题目描述:
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
思路分析:
首先题目要求判断两个链表是否相交,若相交返回相交的起始节点,否侧返回NULL,那么第一个问题如何判断两个链表是否相交呢?其实很简单,遍历两个链表,找到两个链表的最后节点,若两个链表的最后节点相等,那么两个链表一定相交.难就难在如何返还相交起始节点的位置,因为两个链表相交之前的链表是不相等的,如果是相等的话,那我们就可以直接遍历,从这个角度出发,我们在之前判断是否相交时,求出两个链表的长度,因为后半段的长度两个链表一直,那么两个链表的长度差即为长链表领先的节点个数,让长链表先走长度差,再让两个链表同时走,这样就能找到起始相交的节点.如下图:
代码展示:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* curA = headA, *curB = headB;
int lenA = 0, lenB = 0;
while(curA->next)
{
curA = curA->next;
++lenA;
}
while(curB->next)
{
curB = curB->next;
++lenB;
}
//尾节点不相交返回空
if(curA != curB) return NULL;
int gap = abs(lenA - lenB);
struct ListNode* longList = headA, * shortList = headB;
if(lenB > lenA)
{
longList = headB;
shortList = headA;
}
while(gap--)
{
longList = longList->next;
}
while(longList != shortList)
{
longList = longList->next;
shortList = shortList->next;
}
return shortList;
}小结:
这一个专题我准备分两期进行制作,后一期专门进行链表带环问题的讲解,如果觉得对你有帮助的家人们,记得点赞关注哦!