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.

好久不刷的leetcode重新开工。这个题目没什么难度,两个链表如果相交,相交部分必然等长。首先求出两个链表的长度,然后将较长的链表从头部向前移动到和短链表相同长度的结点,然后同时遍历两个链表,如果有交点则返回,没有就返回NULL。

 

 

Solution:


int lengthA = 0, lengthB = 0;
        struct ListNode* ptrA = headA;
        struct ListNode* ptrB = headB;
        while(ptrA != NULL)
        {
                lengthA += 1;
                ptrA = ptrA->next;
        }
        while(ptrB != NULL)
        {
                lengthB += 1;
                ptrB = ptrB->next;
        }
    
        if(lengthA > lengthB)
        {
                int diff = lengthA - lengthB;
                for(int i = 0; i < diff; ++i)
                {
                        headA = headA->next;
                }
        }
        else
        {
                int diff = lengthB - lengthA;
                for(int i = 0; i < diff; ++i)
                {
                        headB = headB->next;
                }
        }
    
        while(headA != NULL && headB != NULL && headA != headB)
        {
                headA = headA->next;
                headB = headB->next;
        }
    
        return headA;
}
36ms

Leave a Reply

Your email address will not be published. Required fields are marked *