编辑代码

// Solution：https://www.cnblogs.com/edisonchou/p/4822675.html

// 公共结点的定义是：内存地址一样的结点，形象表示为
//    1 → 2 → 3
//              ↘
//                 6 → 7 → ...
//              ↗
//        4 → 5

function FindFirstCommonNode(pHead1, pHead2) {
    // write code here
    
	// 空指针
    if(pHead1 === null || pHead2 === null)
		return null;
	// 不是ListNode类型
	if(pHead1.val === undefined || pHead2.val === undefined
	   	|| pHead1.next === undefined || pHead2.next === undefined) {
		return null;	
	}
	
	// 用于遍历链表的指针
	let p1 = pHead1;
	let p2 = pHead2;
	
	// 遍历一遍得到两链表的长度
	let len1 = getListLength(pHead1);
	let len2 = getListLength(pHead2);
	
	// 对齐p1和p2
	if(len1 === 0 || len2 === 0)
		return null;
	
	if(len1 > len2) {
		let e = len1 - len2;
		for(let i=0; i<e; i++)
			p1 = p1.next;
	} else if(len2 > len1) {
		let e = len2 - len1;
		for(let i=0; i<e; i++)
			p2 = p2.next;
	}
	
	console.log('--- after align, p1.val:', p1.val);
	console.log('--- after align, p2.val:', p2.val);
	
	while(p1!==null && p2!==null) {
		if(p1 === p2)
			return p1;
		
		p1 = p1.next;
		p2 = p2.next;
	}
    
	return p1;
}

function getListLength(pHead) {
    let p = pHead;
    let length = 0;
    while(p !== null) {
        length += 1;
        p = p.next;
    }

    return length;
}

// ------------------------------------------------------------
function ListNode(x){
    this.val = x;
    this.next = null;
}

function buildListNode(...vals) {
    let node_h = null;
	let node_p = null;
	
	for(let i=0; i<vals.length; i++) {
		
		let node_new = new ListNode(vals[i]);
		if(node_p === null) {
			node_p = node_new;
			node_h = node_p;
		} else {
			node_p.next = node_new;
			node_p = node_p.next;
		}
		
	}
	
    return node_h;
}

function toStr(pHead) {
    let p = pHead;
    let str = "[ ";
    while(p !== null) {
        str += (p.val+", ");
        p = p.next;
    }
    str += "]";

    return str;
}

// let pHead1 = buildListNode(1,2,3,4,5);
// let pHead2 = buildListNode();

// test -----------------------------------------------
let pHead1 = buildListNode(1,2,3);
let pHead2 = buildListNode(4,5);

let node_6 = new ListNode(6);
let node_7 = new ListNode(7);
node_6.next = node_7;

pHead1.next.next.next = node_6;
pHead2.next.next = node_6;

console.log('LinkedList-1:',toStr(pHead1));
// console.log('LinkedList-1:',getListLength(pHead1));
// 

console.log(pHead1.next.next.next === pHead2.next.next);

let comNode = FindFirstCommonNode(pHead1, pHead2);
if(comNode === null) {
	console.log('No Common Node');
} else {
	console.log('Common Node:', comNode.val);	
}
	
// solution：java ver
/*

// public class ListNode {
//     int val;
//     ListNode next = null;
// 
//     ListNode(int val) {
//         this.val = val;
//     }
// }
public class Solution {
    public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
        // 得到两个链表的长度
        int length1 = GetListLength(head1);
        int length2 = GetListLength(head2);
        int diff = length1 - length2;

        ListNode headLong = head1;
        ListNode headShort = head2;
        if (diff < 0)
        {
            headLong = head2;
            headShort = head1;
            diff = length2 - length1;
        }
        // 先在长链表上走几步
        for (int i = 0; i < diff; i++)
        {
            headLong = headLong.next;
        }
        // 再同时在两个链表上遍历
        while (headLong != null && headShort != null && headLong != headShort)
        {
            headLong = headLong.next;
            headShort = headShort.next;
        }

        ListNode commonNode = headLong;
        return commonNode;
    }
    
    public static int GetListLength(ListNode head)
    {
        int length = 0;
        ListNode tempNode = head;
        while (tempNode != null)
        {
            tempNode = tempNode.next;
            length++;
        }

        return length;
    }
}

*/