[[441326]]

鏈表相交

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

給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回 null 。

圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開(kāi)始相交：

題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。

注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。

示例 1：

示例 2：

示例 3：

思路

簡(jiǎn)單來(lái)說(shuō)，就是求兩個(gè)鏈表交點(diǎn)節(jié)點(diǎn)的指針。這里同學(xué)們要注意，交點(diǎn)不是數(shù)值相等，而是指針相等。

為了方便舉例，假設(shè)節(jié)點(diǎn)元素?cái)?shù)值相等，則節(jié)點(diǎn)指針相等。

看如下兩個(gè)鏈表，目前curA指向鏈表A的頭結(jié)點(diǎn)，curB指向鏈表B的頭結(jié)點(diǎn)：

我們求出兩個(gè)鏈表的長(zhǎng)度，并求出兩個(gè)鏈表長(zhǎng)度的差值，然后讓curA移動(dòng)到，和curB 末尾對(duì)齊的位置，如圖： 

此時(shí)我們就可以比較curA和curB是否相同，如果不相同，同時(shí)向后移動(dòng)curA和curB，如果遇到curA == curB，則找到交點(diǎn)。

否則循環(huán)退出返回空指針。

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的長(zhǎng)度 
            lenA++; 
            curA = curA->next; 
        } 
        while (curB != NULL) { // 求鏈表B的長(zhǎng)度 
            lenB++; 
            curB = curB->next; 
        } 
        curA = headA; 
        curB = headB; 
        // 讓curA為最長(zhǎng)鏈表的頭，lenA為其長(zhǎng)度 
        if (lenB > lenA) { 
            swap (lenA, lenB); 
            swap (curA, curB); 
        } 
        // 求長(zhǎng)度差 
        int gap = lenA - lenB; 
        // 讓curA和curB在同一起點(diǎn)上（末尾位置對(duì)齊） 
        while (gap--) { 
            curA = curA->next; 
        } 
        // 遍歷curA 和 curB，遇到相同則直接返回 
        while (curA != NULL) { 
            if (curA == curB) { 
                return curA; 
            } 
            curA = curA->next; 
            curB = curB->next; 
        } 
        return NULL; 
    } 
}; 

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

其他語(yǔ)言版本

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的長(zhǎng)度 
            lenA++; 
            curA = curA.next; 
        } 
        while (curB != null) { // 求鏈表B的長(zhǎng)度 
            lenB++; 
            curB = curB.next; 
        } 
        curA = headA; 
        curB = headB; 
        // 讓curA為最長(zhǎng)鏈表的頭，lenA為其長(zhǎng)度 
        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; 
        } 
        // 求長(zhǎng)度差 
        int gap = lenA - lenB; 
        // 讓curA和curB在同一起點(diǎn)上（末尾位置對(duì)齊） 
        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: 
        """ 
        根據(jù)快慢法則，走的快的一定會(huì)追上走得慢的。 
        在這道題里，有的鏈表短，他走完了就去走另一條鏈表，我們可以理解為走的快的指針。 
 
        那么，只要其中一個(gè)鏈表走完了，就去走另一條鏈表的路。如果有交點(diǎn)，他們最終一定會(huì)在同一個(gè) 
        位置相遇 
        """ 
        cur_a, cur_b = headA, headB     # 用兩個(gè)指針代替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的長(zhǎng)度 
    for curA != nil { 
        curA = curA.Next 
        lenA++ 
    } 
    for curB != nil { 
        curB = curB.Next 
        lenB++ 
    } 
    var step int 
    var fast, slow *ListNode 
    // 請(qǐng)求長(zhǎng)度差，并且讓更長(zhǎng)的鏈表先走相差的長(zhǎng)度 
    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 
    } 
    // 遍歷兩個(gè)鏈表遇到相同則跳出遍歷 
    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; 
};