首页 > itarticle > leetcode 160. intersection of two linked lists

leetcode 160. intersection of two linked lists

admin 11月 12, 2020 0

Description

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.

Solution

如果两个链表等长，那么只要逐一比较各个节点地址是否相等即可找出第一个公共节点。所以，只要先遍历一遍得到链表的长度，将较长的链表的游标向前移动直到两链表对齐后再同步遍历即可。

Code

class Solution
{
public:
    ListNode *(ListNode *headA, ListNode *headB)
    {
        if(headA == NULL || headB == NULL) return NULL;
        int la = 0, lb = 0;
        ListNode *pa = headA, *pb = headB;
        while(pa)
        {
            pa = pa->next;
            la++;
        }
        while(pb)
        {
            pb = pb->next;
            lb++;
        }
        pa = headA, pb = headB;
        int d = 0;
        printf("la = %d lb = %dn", la, lb);
        if(lb > la)
        {
            d = lb - la;
            for(int i = 0;i < d; i++)
            {
                pb = pb->next;
            }
        }
        else if(lb < la)
        {
            d = la - lb;
            for(int i = 0;i < d; i++)
            {
                pa = pa->next;
            }
        }
        while(pa && pb)
        {
            if(pa == pb)
            {
                return pa;
            }
            pa = pa->next;
            pb = pb->next;
        }
        return NULL;
    }
};