数据结构与算法之链表相交，找交点

链表相交

力扣题目链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci

给你两个单链表的找交点头节点 headA 和 headB ，请你找出并返回两个单链表相交的数据算法起始节点。如果两个链表没有交点，结构交返回 null 。表相

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。找交点

注意，数据算法函数返回结果后，结构交链表必须 保持其原始结构 。表相

示例 1：

示例 2：

示例 3：

思路

简单来说，找交点就是数据算法求两个链表交点节点的指针。这里同学们要注意，结构交交点不是表相数值相等，而是找交点指针相等。

为了方便举例，数据算法假设节点元素数值相等，结构交则节点指针相等。

看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的服务器租用头结点：

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图： 

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

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;     } };  时间复杂度： 空间复杂度：

其他语言版本

Java

public 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) {              //1. swap (lenA, lenB);             int tmpLen = lenA;             lenA = lenB;             lenB = tmpLen;             //2. swap (curA, curB);             ListNode tmpNode = curA;             curA = curB;             curB = tmpNode;         }         // 求长度差         int gap = lenA - lenB;         // 让curA和curB在同一起点上（末尾位置对齐）         while (gap-- > 0) {              curA = curA.next;         }         // 遍历curA 和 curB，遇到相同则直接返回         while (curA != null) {              if (curA == curB) {                  return curA;             }             curA = curA.next;             curB = curB.next;         }         return null;     } } 

Python

class Solution:     def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:         """         根据快慢法则，服务器托管走的快的一定会追上走得慢的。         在这道题里，有的链表短，他走完了就去走另一条链表，我们可以理解为走的快的指针。         那么，只要其中一个链表走完了，就去走另一条链表的路。如果有交点，他们最终一定会在同一个         位置相遇         """         cur_a, cur_b = headA, headB     # 用两个指针代替a和b         while cur_a != cur_b:             cur_a = cur_a.next if cur_a else headB      # 如果a走完了，那么就切换到b走             cur_b = cur_b.next if cur_b else headA      # 同理，b走完了就切换到a         return cur_a 

Go

func getIntersectionNode(headA, headB *ListNode) *ListNode {      curA := headA     curB := headB     lenA, lenB := 0, 0     // 求A，B的长度     for curA != nil {          curA = curA.Next         lenA++     }     for curB != nil {          curB = curB.Next         lenB++     }     var step int     var fast, slow *ListNode     // 请求长度差，并且让更长的链表先走相差的长度     if lenA > lenB {          step = lenA - lenB         fast, slow = headA, headB     } else {          step = lenB - lenA         fast, slow = headB, headA     }     for i:=0; i < step; i++ {          fast = fast.Next     }     // 遍历两个链表遇到相同则跳出遍历     for fast != slow {          fast = fast.Next         slow = slow.Next     }     return fast } 

javaScript

var getListLen = function(head) {      let len = 0, cur = head;     while(cur) {         len++;        cur = cur.next;     }     return len; } var getIntersectionNode = function(headA, headB) {      let curA = headA,curB = headB,         lenA = getListLen(headA),         lenB = getListLen(headB);     if(lenA < lenB) {          [curA, curB] = [curB, curA];         [lenA, lenB] = [lenB, lenA];     }     let i = lenA - lenB;     while(i-- > 0) {          curA = curA.next     }     while(curA && curA !== curB) {          curA = curA.next;         curB = curB.next;     }     return curA; }; 

很赞哦!（437）