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

• 链表基础操作a->c->b b->c->a

题目描述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

C++实现

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

golang实现

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func FindFirstCommonNode( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here

    p1, p2 := pHead1, pHead2
    for p1 != p2 {
        if p1 != nil {
            p1 = p1.Next
        } else {
            p1 = pHead2
        }

        if p2 != nil {
            p2 = p2.Next
        } else {
            p2 = pHead1
        }
    }

    return p1
}