目录
两个链表的第一个公共结点
访问量:839

一、简介

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

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

二、实现

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * 思路:若链表A、B中,存在公共节点,则都从后往前遍历,可能能够找到公共节点
  但单向链表,没法从后往前,只能从距离终点相同且最大长度位置,开始往后逐一比较
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func FindFirstCommonNode( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    if pHead1 == nil || pHead2 == nil {
        return nil
    }
    
    p1,p2 := pHead1,pHead2
    for {
        if p1 == nil {
            // pHead2为最长链表,往后需要往后移动
            for p2 != nil {
                pHead2 = pHead2.Next
                
                p2 = p2.Next
            }
            
            break
        }
        
        if p2 == nil {
            // pHead1为最长链表,往后需要往后移动
            for p1 != nil {
                pHead1 = pHead1.Next
                
                p1 = p1.Next
            }
            
            break
        }
        
        p1 = p1.Next
        p2 = p2.Next
    }
    
    for {
        if pHead1 == nil || pHead2 == nil {
            return nil
        }
        
        if pHead1 == pHead2 {
            return pHead1
        }
        
         pHead1 = pHead1.Next
         pHead2 = pHead2.Next
    }
}