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

相关推荐

不愿透露姓名的神秘牛友
昨天 12:10
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
怎么起名字:早知道就不读书了,害得我送外卖还得扶眼镜
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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