[[441326]]

鏈表相交

力扣題目鏈接：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; 
};