【leetcode每日一题】NO160.Intersection of Two Linked Lists

曾经终败给现在 2022-08-04 01:45 95阅读 0赞

题目：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.

解析：这道题是让我们找到两个单链表的交汇节点，先分别求出两个链表的长度len1和len2，长度大的链表先走|len2-len1|个节点。之后开始遍历两个链表，当两个链表有相同的节点时，即是两个链表的交汇节点，如果没有，则返回null。

代码：

/**
     * 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) {
            int lengthA=0,lengthB=0;
            ListNode *tempA=headA,*tempB=headB;
            while(tempA!=NULL)
            {
                lengthA++;
                tempA=tempA->next;
            }
            while(tempB!=NULL)
            {
                lengthB++;
                tempB=tempB->next;
            }
            ListNode *temp1=headA,*temp2=headB;
            if(lengthA>lengthB)
            {
                for(int i=0;i<lengthA-lengthB;i++)
                    temp1=temp1->next;
            }
            if(lengthA<lengthB)
            {
                for(int i=0;i<lengthB-lengthA;i++)
                    temp2=temp2->next;
            }
            while(temp1!=NULL&&temp2!=NULL)
            {
                if(temp1==temp2)
                    return temp1;
                else
                {
                    temp1=temp1->next;
                    temp2=temp2->next;
                }
            }
            return NULL;
        }
    };