找到两个链表的第一个公共节点（找出两个链表的第一个公共节点）

题目：

还可以先统计两个链表的长度，如果两个链表的长度不一样，就让链表长的先走，直到两个链表长度一样，这个时候两个链表再同时每次往后移一步，看节点是否一样，如果有相等的，说明这个相等的节点就是两链表的交点，否则如果走完了还没有找到相等的节点，说明他们没有交点，直接返回null即可，来画个图看一下。

如图所示:两个链表长度明显不同。

A链表 6-7-8-9 B链表1-2-3-4-8-9. 容易知道A链表长度是4，B链表长度是6。所以让B链表的头结点指针先前进长度2。小夕的读者肯定知道这个2是（6-4）得到的啦。也就是两者链表的差别。所以先让B链表前进2步。

B前进2步。

这样A和B的链表剩余长度就完全一致了。然后就是A和B一起往前一步一步的走，知道两者节点相同，那么就是第一个相同的节点。A和B先同时走一步。

再同时一步。

A和B相遇。

Java语法：

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int x) {

* val = x;

* next = null;

* }

* }

*/

public class Solution {

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

//统计链表A和链表B的长度

int lenA = length(headA), lenB = length(headB);

//如果节点长度不一样，节点多的先走，直到他们的长度一样为止

while (lenA != lenB) {

if (lenA > lenB) {

//如果链表A长，那么链表A先走

headA = headA.next;

lenA--;

} else {

//如果链表B长，那么链表B先走

headB = headB.next;

lenB--;

}

}

//然后开始比较，如果他俩不相等就一直往下走

while (headA != headB) {

headA = headA.next;

headB = headB.next;

}

//走到最后，最终会有两种可能，一种是headA为空，

//也就是说他们俩不相交。还有一种可能就是headA

//不为空，也就是说headA就是他们的交点

return headA;

}

//统计链表的长度

private int length(ListNode node) {

int length = 0;

while (node != null) {

node = node.next;

length++;

}

return length;

}

}

js语法：

// ac地址：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

// 原文地址：https://xxoo521.com/2020-03-12-list-node/

/**

* @param {ListNode} headA

* @param {ListNode} headB

* @return {ListNode}

*/

var getIntersectionNode = function(headA, headB) {

let node = headA;

let lengthA = 0;

while (node) {

++lengthA;

node = node.next;

}

if (!lengthA) return null;

node = headB;

let lengthB = 0;

while (node) {

++lengthB;

node = node.next;

}

if (!lengthB) return null;

let diff = 0,

slow,

fast;

if (lengthA > lengthB) {

slow = headA;

fast = headB;

diff = lengthA - lengthB;

} else {

slow = headB;

fast = headA;

diff = lengthB - lengthA;

}

while (diff--) {

slow = slow.next;

}

while (slow !== fast) {

slow = slow.next;

fast = fast.next;

}

return slow;

};

C++语法：

class Solution {

public:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

ListNode* curA = headA;

ListNode* curB = headB;

int lenA = 0, lenB = 0;

while (curA != NULL) { // 求链表A的长度

lenA++;

curA = curA->next;

}

while (curB != NULL) { // 求链表B的长度

lenB++;

curB = curB->next;

}

curA = headA;

curB = headB;

// 让curA为最长链表的头，lenA为其长度

if (lenB > lenA) {

swap (lenA, lenB);

swap (curA, curB);

}

// 求长度差

int gap = lenA - lenB;

// 让curA和curB在同一起点上（末尾位置对齐）

while (gap--) {

curA = curA->next;

}

// 遍历curA 和 curB，遇到相同则直接返回

while (curA != NULL) {

if (curA == curB) {

return curA;

}

curA = curA->next;

curB = curB->next;

}

return NULL;

}

};

Python语法：

# Definition for singly-linked list.

# class ListNode(object):

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution(object):

def getIntersectionNode(self, headA, headB):

"""

:type head1, head1: ListNode

:rtype: ListNode

"""

len_A = 0

len_B = 0

temp_A = headA

temp_B = headB

while headA:

len_A += 1

headA = headA.next

while headB:

len_B += 1

headB = headB.next

if len_A > len_B:

headA = temp_A

headB = temp_B

for i in range(len_A - len_B):

headA = headA.next

while headA != headB and headA:

headA = headA.next

headB = headB.next

else:

headA = temp_A

headB = temp_B

for i in range(len_B - len_A):

headB = headB.next

while headA != headB and headA:

headA = headA.next

headB = headB.next

if not headA:

return None

else:

return headA