LeetCode Intersection of Two Linked Lists （找交叉点）

题意：

　　给两个链表，他们的后部分可能有公共点。请返回第一个公共节点的地址？若不重叠就返回null。

思路：

　　用时间O(n)和空间O(1)的做法。此题数据弱有些弱。

　　方法（1）假设两个链表A和B，用两个指针分别按顺序遍历AB和BA，这AB和BA肯定等长的。如果他们有公共点，那么按照这样走必定会在某个点相遇。所以只要预先判断是否有公共点，这只需要用两个指针分别指向A和B的链尾判断是否相同即可（这一步可以使用更简单的方法，增加1个计数器，判断指针1是否已经遍历过AB了）。

 /**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}

  * };

  */

 class Solution {

 public:

     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

         ListNode *L1=headA;

         ListNode *L2=headB;

         //若无交点，且AB等长，那么他们会在null处相遇，退出。

         //先判断是否有交点先。

         while(L1&&L1->next) L1=L1->next;

         while(L2&&L2->next) L2=L2->next;

         if(L1!=L2)  return NULL;

         L1=headA;

         L2=headB;

         while(L1!=L2)

         {

             if(L1)  L1=L1->next;

             else    L1=headB;

             if(L2)  L2=L2->next;

             else L2=headA;

         }

         return L1;

     }

 };

AC代码

　　方法（2）先统计链A和B的长度，假设A长，那么指针1先走|A|-|B|步，然后再同时走，若有公共点必定会相遇。

巴特西

LeetCode Intersection of Two Linked Lists （找交叉点）

最新文章

热门文章