首页 > 代码库 > Intersection of Two Linked Lists leetcode

Intersection of Two Linked Lists leetcode

Write a program to find the node at which the intersection of two singly linked lists begins.


For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.


Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.
题目的意思是找到两条链表的相交点,并且返回该节点,如果没有的话,返回NULL

思路:
1、暴力法  直接一个个比较  用两个循环  时间复杂度为 N*M    N M分别为两链表的长度
2、哈希表法: 遍历链表A,并且将节点存储到哈希表中。接着遍历链表B,对于B中的每个节点,查找哈希表,如果在哈希表中找到了,说明是交集开始的那个节点。时间复杂度O(N+M),空间复杂度O(N)或O(M)。

3、双指针法: 定义两个指针,分别指向 headA和headB,分别求出两的链结点个数(长度),然后 temp=abs(numA-numB) 求出两者差,让长的链(max(numA,numB))先走temp步,然后从长的链的当前位置和短链的头部一起往后遍历,知道找到相同的
如上
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
长链为B  ,所以B先走abs(6-5)=1步   长链的当前位置为  b2   ,然后 A从头  a1  两指针 一起往后走

双指针方法的一种变形方法:
上面需要先遍历A   B  一次  ,如果第一次遍历得时候让 A跟B一起走  ,有一个为NULL就停下
那么此时短链已经走完了,  长链  走了 短链的长度,剩下的长度就为   两条链的长度差       

如上       
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
此时  B的当前位置为   c3     然后指向A的指针指向b1(没有走完的头部)  当前位置和指向A的指针   同时往后走   ,当前位置指向NULL结束  ,指向A的指针此时指向b2  ,也就是上面求的 先走长度差步的位置,然后再按照剩下的走完,找到交点

代码如下:  

<span style="font-size:18px;">/**
 * 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) {
        
        if(headA==NULL||headB==NULL)
            return NULL;
        ListNode *p,*q;
        p=headA;
        q=headB;
        
        int numA=0;  //定义numA用来记录headA的链结点个数
        int numB=0;//定义numB用来记录headB的链结点个数
        
        while(p)
        {
            ++numA;
            p=p->next;
        }
        while(q)
        {
            ++numB;
            q=q->next;
        }
        
        
        p=headA;
        q=headB;
        int temp=abs(numA-numB);
        if(numA>numB) //判断哪个链长,长的那根链先走 |numA-numB| 步
        {
            while(temp>0)
            {
                p=p->next;
                --temp;
            }
        }
        else
        {
            while(temp>0)
            {
                q=q->next;
                --temp;
            }
        }
        while(p&&q)  //长的走完之后  , 两者一起走  直到遇到重叠的节点
        {
            if(p==q)
                return p;
            p=p->next;
            q=q->next;
        }
        return NULL;
        
    }
};</span>



Intersection of Two Linked Lists leetcode