【数据结构】_单链表_相关面试题（二）

本章重点

hello友友们~
今天我们将对单链表的后半部分的相关面试题进行详细解析，下面就跟着我一起开启吧~
really GO！

1.相交链表

题目：
输入两个链表，找出它们的第一个公共结点。

代码分析：

//找到相交结点，相交链表
SListNode* getIntersectionNode(SListNode* head_a, SListNode* head_b)
{//求两个链表的长度SListNode* cur_a = head_a;int la = 0;while (cur_a){la++;cur_a = cur_a->next;}SListNode* cur_b = head_b;int lb = 0;while (cur_b){lb++;cur_b = cur_b->next;}//默认任为a长b短SListNode* longList = head_a;SListNode* shortList = head_b;//上面假设错误就是b长a短if (lb > la){longList = head_b;shortList = head_a;}//求间距 abs表绝对值int gap = abs(la - lb);//先让长的走和短的之间相差的步数while (gap--){longList = longList->next;}//上面走完之后就一样长，然后随便以一个为准while (longList){//比较的是地址而非数值if (longList == shortList){return longList;}//否则longList = longList->next;shortList = shortList->next;}return NULL;
}void test4()
{SListNode* n1 = Great_SListNode(1);SListNode* n2 = Great_SListNode(2);SListNode* n3 = Great_SListNode(3);SListNode* n4 = Great_SListNode(4);SListNode* n5 = Great_SListNode(5);SListNode* n6 = Great_SListNode(6);SListNode* n7 = Great_SListNode(7);SListNode* n8 = Great_SListNode(8);//A:1 2 3 4 5 6 7 8SListNode* n9 = Great_SListNode(9);SListNode* n10 = Great_SListNode(10);//B:9 10 6 7 8n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = n6;n6->next = n7;n7->next = n8;n9->next = n10;n10->next = n6;//注意！！！printf("List A: ");SLPrint(n1);printf("List B: ");SLPrint(n9);// 查找交点并打印SListNode* intersect = getIntersectionNode(n1, n9);printf("Intersection node: ");SLPrint(intersect);  // 应输出6->7->8->NULL}
int main()
{test4();
}

详细解析：

• 计算两个链表的长度：通过遍历两个链表，分别计算出它们的长度la和 lb。
• 确定长链表和短链表：默认假设head_a是长链表，head_b 是短链表。如果 lb > la，则交换长链表和短链表。
• 计算长度差：计算两个链表的长度差 gap。
• 让长链表先走gap步：使长链表和短链表的剩余长度相等。
• 同时遍历两个链表：比较长链表和短链表的节点，如果找到相同的节点，则返回该节点；如果遍历完都没有找到相同的节点，则返回 NULL。

❗❗❗注意：

abs不是求绝对值吗？那是不是就不用判断la lb谁长谁短了？

abs函数只是计算差值的绝对值，而判断la和lb的长短是为了确定哪个链表是长链表，哪个是短链表，从而正确地让长链表指针先移动， 确保算法能够正确找到相交节点。 所以判断长短这一步骤是必不可少的。

打印结果：

🤔🤔🤔补充说明：

为什么比较地址而不是对应的数值呢⚙️⚙️⚙️

• 💡在链表相交的问题里，我们要找的是两个链表共同拥有的节点，也就是在内存中是同一个节点的情况。因为两个链表相交意味着它们从某个节点开始会共享后续的所有节点，这些共享节点在内存里只有一份，不同链表的指针会指向这个相同的内存地址。
• 💡要是比较节点存储的数值，即便两个节点的值相同，它们也可能是内存中不同位置的两个独立节点，并非真正的相交节点。所以，比较地址才能准确找出两个链表的相交节点。
• if (longList == shortList)：当longList和shortList指向同一个节点时，意味着找到了相交节点，此时返回该节点的指针。由于是通过比较指针地址来判断是否为同一个节点，所以只要两个指针指向同一块内存，就表明找到了相交点。
  - longList = longList->next; shortList = shortList->next;：若当前节点不是相交节点，就将两个指针都向后移动一位，继续比较下一个节点。
• return NULL;：若遍历完整个链表都没有找到相交节点，就返回 NULL。

2.环形链表

题目：

代码分析：

/环形链表
//判断链表是否有环bool hasCycle(SListNode* head)
{//空链表不能有环if (head == NULL) {return false;}//快慢指针SListNode* slow = head;SListNode* fast = head;//让快指针可以走while (fast && fast->next){slow = slow->next;fast = fast->next->next ;if (slow == fast){return true;}}return  false;
}
void test5()
{SListNode* n1 = Great_SListNode(1);SListNode* n2 = Great_SListNode(2);SListNode* n3 = Great_SListNode(3);SListNode* n4 = Great_SListNode(4);SListNode* n5 = Great_SListNode(3);SListNode* n6 = Great_SListNode(2);SListNode* n7 = Great_SListNode(1);n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = n6;n6->next = n7;n7->next = n2;if (hasCycle(n1)) {printf("The linked list has a cycle.\n");}else {printf("The linked list does not have a cycle.\n");}
}int main()
{test5();
}

画图分析：

详细解析：

• 初始化快慢指针：定义两个指针slow和 fast，都初始化为链表的头指针 head。
• 循环遍历链表：使用while循环，条件为fast和fast->next都不为 NULL。这是因为快指针每次要移动两步，所以需要确保它的下一个节点也存在。
• 移动快慢指针：在循环中，慢指针slow每次移动一步，即 slow = slow->next；快指针fast每次移动两步，即 fast = fast->next->next。
• 判断是否相遇：在每次移动指针后，检查slow和fast是否相等。如果相等，说明快慢指针相遇了，也就意味着链表中存在环，此时返回 true。
• 循环结束条件：如果循环结束都没有出现slow和fast相等的情况，说明链表中不存在环，返回 false。

代码运行：

3.找到环点

题目：

画图分析：

代码分析：

 //找到环点//用于检测链表是否存在环，并找出环的起始节点SListNode* detectCycle(SListNode* head){//定义快慢指针SListNode* slow = head;SListNode* fast = head;//使用 while 循环来让快慢指针移动while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (fast == slow){break;//相遇，链表存在环，跳出循环}}//判断链表是否有环if (fast==NULL || fast->next ==NULL){return NULL;//没有环}SListNode* meet = fast;//将相遇点赋值给meet指针//找到环的起点while (head != meet){head = head->next;meet = meet->next;}return meet;//若链表存在环，返回环的起始节点指针；若不存在环，返回 NULL}
void test5()
{SListNode* n1 = Great_SListNode(1);SListNode* n2 = Great_SListNode(2);SListNode* n3 = Great_SListNode(3);SListNode* n4 = Great_SListNode(4);SListNode* n5 = Great_SListNode(3);SListNode* n6 = Great_SListNode(2);SListNode* n7 = Great_SListNode(1);n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = n6;n6->next = n7;n7->next = n2;SListNode* cycleStart = detectCycle(n1);if (cycleStart) {printf("Cycle starts at node with value: %d\n", cycleStart->val);}else {printf("No cycle found.\n");}}int main()
{test5();
}

详细解析：

• 初始化两个指针slow和fast都指向链表的头节点。
• 使用while循环，只要fast指针和fast->next不为空，就继续循环。在循环中，slow 指针每次移动一步，fast 指针每次移动两步。
• 如果slow指针和fast指针相遇，说明链表存在环，跳出循环。
• 检查fast指针和fast->next是否为空，如果为空，这表明快指针已经到达链表末尾，意味着链表不存在环，此时返回 NULL，说明链表没有环，返回 NULL。
• 将相遇点赋值给meet指针。
• 让head指针和meet指针同时移动，每次移动一步，直到它们相遇。相遇点就是环的起始节点，返回该节点。

🤔🤔🤔思考一个问题
这里跳出第一个while循环后为什么还要if判断是否有环呢 ，不是相遇了就代表有环吗？？？

原因：
while (fast && fast->next) 这个循环存在两种跳出的情况：

1. 快慢指针相遇：当 fast 指针和 slow 指针在环中相遇时，执行 break 语句跳出循环，这种情况表明链表存在环。
2. 快指针走到链表末尾：当链表不存在环时，快指针 fast 或者 fast->next 最终会变为 NULL，此时循环条件不满足，循环自然结束，这种情况表明链表没有环。

总结：
while 循环结束后，我们无法直接确定是哪种情况导致循环结束。所以需要通过 if (fast == NULL || fast->next == NULL) 这个判断来区分

4.复杂链表的复制

题目：

这道题的核心目标是复制一个复杂链表，其中每个节点除了有指向下一个节点的 next 指针外，还有一个指向链表中任意节点或 NULL 的 random 指针。其核心原理是通过巧妙的链表结构调整，在不使用额外数据结构（如哈希表）的情况下，高效地完成复制。

代码分析:
注意这里结构体中新定义了一个random

💡💡💡整体思路
该函数主要通过三个步骤完成复杂链表的复制：

1. 在原链表的每个节点后面插入一个复制节点。
2. 设置复制节点的 random 指针。
3. 拆分原链表和复制链表，得到独立的复制链表。

//复杂链表的复制
SListNode* copyRandomList(SListNode* head)
{if (head == NULL){return NULL;//如果原链表为空，直接返回 NULL，因为空链表没有节点需要复制。}//1.拷贝节点，链接到原节点的后面SListNode* cur = head;while (cur){SListNode* copy = (SListNode*)malloc(sizeof(SListNode));copy->next = NULL;copy->random = NULL;copy->val = cur->val;SListNode* next = cur->next;cur->next = copy;copy->next = next;cur = next;}//2.处理拷贝节点的randomcur = head;while (cur){SListNode* copy = cur->next;if (cur->random)//不为空{copy->random = cur->random->next;//copy的random等于cur的random的下一个}else{copy->random = NULL;}cur = cur->next->next;}//3.拆解出复制链表cur = head;SListNode* copyHead = head->next;while (cur){SListNode* copy = cur->next;SListNode* next = copy->next; cur->next = next;if (next)//next不为空{copy->next = next->next;}else{copy->next = NULL;}cur = next;}return copyHead;
}void test6()
{SListNode* n1 = Great_SListNode(1);SListNode* n2 = Great_SListNode(2);SListNode* n3 = Great_SListNode(3);SListNode* n4 = Great_SListNode(4);SListNode* n5 = Great_SListNode(5);n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = NULL;n1->random = NULL;n2->random = n1;n3->random = n5;n4->random = n3;n5->random = n1;SListNode* newnode = copyRandomList(n1);SLPrint(newnode);
}int main()
{test6();
}

详细解析：

1. 拷贝节点，链接到原节点的后面
   

2. 处理拷贝节点的random
   

3. 拆解出复制链表
   

运行结果：

(表示拷贝链表的每个节点的 val 和 random 指向与原链表完全一致。)

题目要求我们深度复制一个带有 next 和 random 指针的链表。关键在于：

• 普通链表的复制：直接遍历并逐个拷贝节点即可。

• random 指针的挑战：random 可能指向任意节点，拷贝时必须保持与原链表相同的指向关系。

问题：为什么复杂链表难以复制？

普通链表的复制只需遍历一次，逐个节点创建并连接即可。但复杂链表的难点在于 random 指针：

• random 指针的任意性：它可能指向链表中的任意节点，无法在一次遍历时直接确定复制后的目标节点。
• 传统方法的局限性：若用哈希表保存原节点与复制节点的映射关系，虽然可行，但空间复杂度为 (O(n))。本题的目标是优化到 (O(1)) 空间复杂度。

5.删除链表中重复的结点

题目：

代码分析：

//删除链表中重复的结点
SListNode* deleteDuplication(SListNode* head)
{//如果链表为空或者链表中只有一个节点 那么不存在重复节点 直接返回原链表头指针if (head == NULL || head->next == NULL){return head;//表示不需要处理}SListNode* prev = NULL;SListNode* cur = head;SListNode* next = cur->next;//遍历链表while (next)//只要next不为NULL就继续处理{//如果cur和next的值不相等 说明当前节点的值不重复if (cur->val != next->val){prev = cur;//将 prev 指向 curcur = next;//cur指向nextnext = next->next;//next指向下一个节点 继续向后遍历}//当前节点和下一个节点的值相同else{//找到第一个与当前节点值不同的节点while (next && cur->val == next->val){next = next->next;//不断将next指针向后移动 直到找到第一个与cur值不同的节点}//如果prev不为 NULL说明重复节点不是从链表头开始的if (prev){prev->next = next;}//为空else{//说明重复节点从链表头开始，将 head 指针指向 next，更新链表的头节点head = next;}//释放while (cur != next){//先保存cur,然后找到后面的一个节点，否则先释放的话就找不到后一个相同的结点SListNode* del = cur;cur = cur->next;free(del);}if (next)//如果next不为 NULL，将next指针向后移动一位{next = next->next;}}}return head;
}void test7()
{SListNode* n1 = Great_SListNode(1);SListNode* n2 = Great_SListNode(1);SListNode* n3 = Great_SListNode(1);SListNode* n4 = Great_SListNode(4);SListNode* n5 = Great_SListNode(5);SListNode* n6 = Great_SListNode(5);SListNode* n7 = Great_SListNode(5);n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = n6;n6->next = n7;n7->next = NULL;SLPrint(n1);SListNode*phead=deleteDuplication(n1);SLPrint(phead);
}int main()
{test7();
}

详细解析：

运行结果：

🎉🎉🎉

在这里本章就完结啦~

撒花~ 友友们 我们下期见！
★,°:.☆(￣▽￣)/$:.°★