题解 | #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
全部评论

相关推荐

哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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