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

Intersection of Two Linked Lists--leetcode

原题链接:https://oj.leetcode.com/problems/intersection-of-two-linked-lists/

题目大意:给定两个单链表,若相交则找出第一个交点。

解题思路:如果两个无环单链表相交,则必定尾部结点为同一个结点。设定两个指针,若从两个链表的表头同时遍历,很明显不能找到交点。但若将较长的链表截去长出来的一部分,然后两个指针同时遍历,则第一次两个指针相等的结点明显是所求结点。若走到链表尾,任然未相交,则两个链表未相交。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL||headB==NULL)
            return NULL;
        ListNode *p1,*p2;
        p1=headA,p2=headB;
        int lenA=0,lenB=0;
        while(p1){
            lenA++;
            p1=p1->next;
        }
        while(p2){
            lenB++;
            p2=p2->next;
        }
        p1=headA,p2=headB;
        while(lenA<lenB){
            p2=p2->next;
            lenA++;
        }
        while(lenB<lenA){
            p1=p1->next;
            lenB++;
        }
        while(p1&&p2){
            if(p1==p2)
                return p1;
            p1=p1->next;
            p2=p2->next;
        }
        return NULL;
    }
};

因为没有环,所以题目比较简单。题目比较经典,可以扩展到有环的情况下,大家可以考虑下哈。

Intersection of Two Linked Lists--leetcode