力扣每日一道系列 --- LeetCode 160. 相交链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣每日一道系列 --- LeetCode 160. 相交链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣每日一道系列 --- LeetCode 160. 相交链表,LeetCode每日一道,leetcode,链表,算法

📷 江池俊：个人主页 🔥个人专栏： ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人，再渺小也不会迷途。

LeetCode 160. 相交链表

力扣每日一道系列 --- LeetCode 160. 相交链表,LeetCode每日一道,leetcode,链表,算法

思路：
首先计算两个链表的长度，然后判断两个链表的尾节点是否相同。如果不同，那么这两个链表就没有交集，返回空；如果相同，那么就通过计算两个链表的长度差，让长链表先走差距步，然后两个链表一起走，直到它们相遇。

具体步骤如下：

初始化两个指针 cur1 和 cur2 分别指向 headA 和 headB，即两个链表的头节点。同时，初始化两个变量 lenA 和 lenB 分别用来计算两个链表的长度。

通过循环计算 lenA 和 lenB，这里的循环是计算链表的长度，cur1 和 cur2 分别最后会指向链表的尾节点。

判断 cur1 和 cur2 是否相等，如果不同，说明两个链表没有交集，返回空。

如果 cur1 和 cur2 相等，说明两个链表有交集。这时需要确定哪个链表长，哪个链表短。长链表先走差距步，使两个链表的尾节点对齐。

通过循环让长链表先走差距步，这里的差距 n 是两个链表长度的差。

然后两个链表一起走，直到它们相遇。

当 longList 和 shortList 相遇时，返回相遇节点。

时间复杂度：O(m+n)
空间复杂度：O(1)

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
      struct ListNode *cur1 = headA;
      struct ListNode *cur2 = headB;
      int lenA = 1,lenB = 1;
      while(cur1->next)//计算第一个链表的长度
      {
          cur1 = cur1->next;
          lenA++;
      }
      while(cur2->next)//计算第二个链表的长度
      {
          cur2 = cur2->next;
          lenB++;
      }
      if(cur1!=cur2)//判断两个链表的尾节点是否相同
      {
          return NULL;
      }

      int n = abs(lenA-lenB);//得到差距步
      struct ListNode *longList = headA;
      struct ListNode *shortList = headB;
      if(lenA<lenB)
      {
          longList = headB;
          shortList = headA;
      }

      while(n--)//先走差距步
      {
          longList = longList->next;
      }
      //一起走
      while(longList!=shortList)
      {
          longList = longList->next;
          shortList = shortList->next;
      }
      return longList;
}