C语言中链表经典面试题目

🐶博主主页：@ᰔᩚ. 一怀明月ꦿ

❤️‍🔥专栏系列：线性代数，C初学者入门训练，题解C，C的使用文章，「初学」C++

🔥座右铭：“不要等到什么都没有了，才下定决心去做”

🚀🚀🚀大家觉不错的话，就恳求大家点点关注，点点小爱心，指点指点🚀🚀🚀

链表分割

链表的回文结构

相交链表

链表分割

描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

自测输入:

{1,1,3,2,4},2

实际输出

{1,1,3,2,4}

自测输入:

{1,1,3,1,4},2

实际输出

{1,1,1,3,4}

解题思路：

整体思路是，创建两个头指针head和phead，head连接小于x的节点，phead连接大于等于x的节点，最后head连接的尾节点指向phead连接的头节点。
class Partition 
{
public:ListNode* partition(ListNode* pHead, int x) {if(pHead==NULL){return NULL;}// write code hereListNode* head=NULL;ListNode* n1=NULL;ListNode* phead=NULL;ListNode* n2=NULL;ListNode* cur=pHead;while(cur){if(cur->val<x){if(head==NULL){head=n1=cur;}else {n1->next=cur;n1=n1->next;}cur=cur->next;}else {if(phead==NULL){phead=n2=cur;}else {n2->next=cur;n2=n2->next;}cur=cur->next;}}if(n2!=NULL){n2->next=NULL;}if(head==NULL){return phead;}n1->next=phead;return head;}
};

链表的回文结构

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

解题思路：

找到链表的中间节点，然后将中间节点包括以后的节点进行逆置，逆置后得到一个头指针，然后依次判断原头指针连接的节点的值和现在得到的头指针连接的节点的值进行比较。这里不需要担心，链表的节点数的奇偶性。

#include <cstddef>
class PalindromeList {
public:bool chkPalindrome(ListNode* A){// write code hereListNode* cur=A;int count =0;while(cur){cur=cur->next;count++;}int num=count/2;ListNode* tail=A;ListNode* prev=NULL;ListNode* head=NULL;ListNode* n1=A;while(num){num--;tail=tail->next;}n1=tail;prev=tail->next;while(n1){n1->next=head;head=n1;n1=prev;if(prev!=NULL){prev=prev->next;}}while(head){if(A->val!=head->val){return false;}head=head->next;A=A->next;}tail=NULL;return true;}
};这里是将原来的，找中间节点和逆置的函数进行复用
// #include <cstddef>
// class PalindromeList {
// public:
// struct ListNode* reverseList(struct ListNode* head)
// {
//     if(head==NULL)
//     {
//         return NULL;
//     }
//     struct ListNode* n1=NULL;
//     struct ListNode* n2=head;
//     struct ListNode* n3=head->next;
//     while(n2)
//     {
//         n2->next=n1;
//         n1=n2;
//         n2=n3;
//         if(n3!=NULL)
//         {
//             n3=n3->next;
//         }
//     }
//     return n1;
// }
// struct ListNode* middleNode(struct ListNode* head)
// {
//     struct ListNode* cur=head;
//     int count=0;
//     while(cur)
//     {
//         cur=cur->next;
//         count++;
//     }
//     int num=count/2;
//     cur=head;
//     while(num--)
//     {
//         cur=cur->next;
//     }
//     return cur;
// }
// bool chkPalindrome(ListNode* A)
//    {
//         // write code here
//         ListNode* mid=middleNode(A);
//         ListNode* remid=reverseList(mid);
//         while(remid)
//         {
//             if(A->val!=remid->val)
//             {
//                 return false;
//             }
//             A=A->next;
//             remid=remid->next;
//         }
//         return true;
//    }
// };

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

解题思路：

判断两个链表是否相交的关键在于，两个链表的尾节点是否相等（这里指的是为节点的地址，而不是值），相等的话，则两个链表必定相交。如果相交的话，就需要找交点，找交点有两种方法，第一种（暴力求解）：A链表所有节点跟B链表的所有节点比较一遍，相等的就是交点，但是时间复杂度为O(N*M)。第二种：分别得到两个链表的长度LA和LB，长的先走abs(LA-LB)步，然后两个同时走，第一个相等的就是交点。
//判断链表是否相交，重点在于判断节点的地址是否相等
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode* tail1=headA;struct ListNode* tail2=headB;int lenA=1,lenB=1;while(tail1->next){tail1=tail1->next;lenA++;}while(tail2->next){tail2=tail2->next;lenB++;}//如果尾节点不相等，一定不相交if(tail1!=tail2){return NULL;}//长先走差距步int gap=abs(lenA-lenB);struct ListNode* longList=headA;struct ListNode* shortList=headB;if(lenA<lenB){longList=headB;shortList=headA;}while(gap--){longList=longList->next;}while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return longList;
}