题解 | #JZ52-两个链表的第一个公共结点#

两个链表的第一个公共结点

http://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46

1.题解

让两个节点都从两条链的开端往后走,每个都走一个单位。

最后两个节点要么都是NULL(无公共结点),要么是得到公共结点。

可以假设一下,两条链如果长度相同,那么走到最后就是NULL,就对应无公共结点。

如果链不相同,那么肯定也会多走几遍,使得对应无公共结点。

如果链有公共结点,那么肯定会交于公共结点,类似于上述交于NULL。

1.1 C++

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *p1 = pHead1;
        ListNode *p2 = pHead2;
        
        while(p1 != p2) {
            if (p1 == NULL) p1 = pHead1;
            else p1 = p1->next; 
                
            if (p2 == NULL) p2 = pHead2;
            else p2 = p2->next;
        }  
        
        return p1;
    }
};

1.2 Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        p1 = pHead1
        p2 = pHead2
        
        while p1 != p2:
            p1 = p1.next if p1 else pHead1
            p2 = p2.next if p2 else pHead2  
            
        return p1
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:58
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务