算法刷题_链表篇

算法刷题Day8_链表相交

文章目录

• 算法刷题Day8_链表相交
• • @[TOC](文章目录)
• 前言
• 一、求出两个链表的长度和差值
• 二、让其中较长一个链表移动到和第二链表对齐的位置
• 三、其他解法_双指针法：
• 总结

前言

简单来说，就是求两个链表交点节点的指针。

一、求出两个链表的长度和差值

ListNode *curA = headA;
ListNode *curB = headB;
int lenA=0,lenB=0;
while(curA!=NULL){// 求链表A的长度
	len++;
	curA=curA->next;
}
while(curB!=NULL){/ 求链表B的长度
	len++;
	curB=curB->next;
}
curA=headA;
curB=headB;
 // 让curA为最长链表的头，lenA为其长度
if（lenB>lenA）{
	swap(lenA,lenB);
	swap(curA,curB);
int gap=lenA-lenB;

二、让其中较长一个链表移动到和第二链表对齐的位置

由于对齐后后面的元素都需要相等，就移动长的那个链表的指针到与短链表能一一对应的地方，开始逐个比较。

代码如下（示例）：

while(gap--){
	curA=curA->next;
}
  // 遍历curA 和 curB，遇到相同则直接返回
  while(curA!=NULL){
  	if(curA=curB){
  		return curA;
  	}
  	curA=curA->next;
  	curB=curB->next;
  	}
  	return NULL;
}
  

三、其他解法_双指针法：

假设链表的结构：
链表 A 的长度为 m，链表 B 的长度为 n。
两链表的相交部分长度为 c，且交点前链表 A 有部分长度为 a，链表 B 有部分长度为 b。
m = a + c
n = b + c
指针的路径：
指针 pA 的完整路径：a + c + b + c（遍历 A 后切换到 B）
指针 pB 的完整路径：b + c + a + c（遍历 B 后切换到 A）
两条路径的总长度是相同的：
a + c + b + c = b + c + a + c。
因此，无论两个链表的长度差多少，两个指针最终会在 交点处 相遇，或者同时到达 nullptr（没有交点的情况）。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) {
            return nullptr; // 如果任一链表为空，直接返回 null
        }

        // 初始化两个指针
        ListNode* pA = headA;
        ListNode* pB = headB;

        // 遍历两个链表
        while (pA != pB) {
            // 如果当前指针到达链表末尾，则切换到另一个链表的头部
            pA = (pA == nullptr) ? headB : pA->next;
            pB = (pB == nullptr) ? headA : pB->next;
        }

        // 返回相交节点或 null
        return pA;
    }
};

总结

推荐使用双指针法：它更简洁、高效，不需要显式计算链表长度。在需要快速实现时，双指针法是更好的选择。学习或演示可以用长度对齐法：长度对齐法的逻辑更直观，更容易理解。适合用于学习链表操作或展示思路。