題目一.png

題目二.png

解決思路

思路一

遍歷兩個(gè)鏈表到末尾節(jié)點(diǎn)屎媳，同時(shí)分別對(duì)兩個(gè)鏈表長(zhǎng)度計(jì)數(shù)夺溢，判斷末尾節(jié)點(diǎn)是否相同论巍，相同則說(shuō)明交叉，將長(zhǎng)的鏈表先移動(dòng)長(zhǎng)度差個(gè)節(jié)點(diǎn)风响，同時(shí)遍歷兩個(gè)鏈表嘉汰，第一個(gè)相同節(jié)點(diǎn)即為所求。
注意状勤，可能短鏈表是長(zhǎng)鏈表的一部分鞋怀，或者兩個(gè)鏈表完全一樣。
example ：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL|| headB == NULL ) return NULL;
        int cntA=0;
        int cntB=0;
        ListNode* curA=headA;
        ListNode* curB=headB;
        int sub=0;
        while(1)
        {
            if(!curA->next&&!curB->next)
                break;
            if(curA->next)
            {
                cntA++;
                curA=curA->next;
            }
            if(curB->next)
            {
                cntB++;
                curB=curB->next;
            }
        }
        if(curA!=curB)
            return NULL;
        curA=headA;
        curB=headB;
        if(cntA>cntB)
        {
             sub=cntA-cntB;
             
             while(sub)
             {
                 curA=curA->next;
                 sub--;
             }

        }
        else
        {
            sub=cntB-cntA;
            while(sub)
            {
                curB=curB->next;
                sub--;
            }
        }
        while(curA!=curB)
        {
            curA=curA->next;
            curB=curB->next;
        }
        return curA;
    }
};

思路二

將第一個(gè)鏈表的末尾節(jié)點(diǎn)指向第二個(gè)節(jié)點(diǎn)的頭部（返回結(jié)果前要拆開(kāi)）持搜，問(wèn)題轉(zhuǎn)換為求單鏈表是否有環(huán)密似，環(huán)入口即為所求交叉點(diǎn)。
合并后的單鏈表頭為第一個(gè)鏈表的頭葫盼，判斷是否有環(huán)的方式為残腌，定義兩個(gè)指針，一個(gè)slow贫导，每次前進(jìn)一步抛猫，一個(gè)fast，每次前進(jìn)兩步孩灯，
直至slow == fast 或者 fast走到末尾闺金，slow==fast說(shuō)明有環(huán)，fast走到末尾說(shuō)明無(wú)環(huán)峰档。判斷有環(huán)后败匹，定義兩個(gè)指針，一個(gè)指向剛才的相遇點(diǎn)讥巡，一個(gè)指向合并后的鏈表頭掀亩，相等即為環(huán)入口（兩個(gè)鏈表組成一個(gè)循環(huán)單鏈表情況），兩個(gè)指針每次移動(dòng)一步尚卫，直到找到相同點(diǎn)归榕，即為環(huán)入口。

判斷環(huán)方式吱涉，求環(huán)入口方法證明略刹泄。

example：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    
    var last *ListNode
    
    for cur := headA; ; {
        if cur.Next == nil {
            last = cur
            cur.Next = headB
            break
        }
        cur = cur.Next
    }
    
    fast, slow := headA, headA
    find := false
    for ; fast != nil && fast.Next != nil;  {
        slow = slow.Next;
        fast = fast.Next.Next;
        if slow == fast {
            find = true
            break
        }
    }
    if ! find {
        last.Next = nil
        return nil
    }else {
        fast = headA
        for {
            if slow == fast {
                last.Next = nil
                return slow
            }
            slow = slow.Next
            fast = fast.Next
        }
    }
}