leetcode 链接：剑指 Offer 52. 两个链表的第一个公共节点
相同题目：
[容易] 160. 相交链表

题目

输入两个链表，找出它们的第一个公共节点。

注意：

  • 如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解答 & 代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. private:
  11.     int calListLen(ListNode* head)
  12.     {
  13.         int len = 0;
  14.         ListNode* cur = head;
  15.         while(cur != NULL)
  16.         {
  17.             ++len;
  18.             cur = cur->next; 
  19.         }
  20.         return len;
  21.     }
  22. public:
  23.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  24.         if(headA == NULL || headB == NULL)
  25.             return NULL;
  27.         int lenA = calListLen(headA);
  28.         int lenB = calListLen(headB);
  29.         ListNode* curA = headA;
  30.         ListNode* curB = headB;
  31.         if(lenA > lenB)
  32.         {
  33.             for(int i = 0; i < lenA - lenB; ++i)
  34.                 curA = curA->next;
  35.         }
  36.         else
  37.         {
  38.             for(int i = 0; i < lenB - lenA; ++i)
  39.                 curB = curB->next;
  40.         }
  41.         while(curA != NULL && curB != NULL)
  42.         {
  43.             if(curA == curB)
  44.                 return curA;
  45.             curA = curA->next;
  46.             curB = curB->next;
  47.         }
  48.         return NULL;
  49.     }
  50. };

执行结果：

执行结果：通过

执行用时：36 ms, 在所有 C++ 提交中击败了 98.26% 的用户
内存消耗：14.2 MB, 在所有 C++ 提交中击败了 67.11% 的用户