首页 > 其他 > 详细

Intersection of Two Linked Lists

时间:2015-03-05 23:37:28      阅读:329      评论:0      收藏:0      [点我收藏+]

编程之美上有这题,先计算这两链表的长度,然后从这两链表长度相等处扫一遍,找到相同节点就跳出即可。

O(n)的时间复杂度 O(1)的空间开销

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
     struct ListNode *p1 = headA,*p2 = headB,*p = NULL;
        int lenA = 0 , lenB = 0;
        while(p1){
            p1 = p1->next;
            lenA++;
        }
        while(p2){
            p2 = p2->next;
            lenB++;
        }
         p1 = headA;p2 = headB;
        if(lenA>lenB){
            for(int i = 0 ; i < lenA-lenB ; i++){
                p1 = p1->next;
            }
        }else {
            for(int i = 0 ; i <lenB-lenA ; i++){
                p2 = p2->next;
            }
        }
        for(;p1;p1 = p1->next,p2 = p2->next){
            if(p1 == p2){
                p = p1;
                break;
            }
        }
        return p;
}

 

Intersection of Two Linked Lists

原文:http://www.cnblogs.com/llei1573/p/4316901.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!