• 題目：
  Write a program to find the node at which the intersection of two singly linked lists begins.
  For example, the following two linked lists:

A:     a1 → a2
                     ↘
                       c1 → c2 → c3
                     ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null

• The linked lists must retain their original structure after the function returns.

• You may assume there are no cycles anywhere in the entire linked structure.

• Your code should preferably run in O(n) time and use only O(1) memory.

• 分析：
  兩個鏈表，如圖會從某個位置開始進(jìn)行重合，求出這個起始交點(diǎn)，需要注意的是：

  • 沒有交點(diǎn)，返回NULL
  • 保持原來的結(jié)構(gòu)不變
  • 確保沒有環(huán)
  • 時間復(fù)雜度為O（n），空間復(fù)雜度為O（1）

  其中第一條和最后一條注意事項是最重要的，個人覺得這道題雖然在LeetCode上面是easy難度的，但是涉及到的內(nèi)容還是挺不少的，因為有最后一條注意事項的限制，所以需要結(jié)合時間復(fù)雜度和空間復(fù)雜度來進(jìn)行算法定制，對于本題，本文一共會列出三種算法來求解，并同時分析算法復(fù)雜度和時間復(fù)雜度。

• 三種算法的分析：

  1. 直接法：
     遍歷鏈表A，對于每一個遍歷的節(jié)點(diǎn)都遍歷一次鏈表B，判斷是否有節(jié)點(diǎn)相同，這種算法是最簡單的，但是效率不高
  • 時間復(fù)雜度：O（n * n）
  • 空間復(fù)雜度：O（1）

  顯然是不能滿足要求的，時間復(fù)雜度不是一個級別的

  2. 哈希表求解法
     先遍歷鏈表A，將鏈表A的每個節(jié)點(diǎn)放入哈希表中，然后遍歷鏈表B，對于每個節(jié)點(diǎn)都利用哈希表進(jìn)行判斷，看是否存在相同的節(jié)點(diǎn)
  • 時間復(fù)雜度：O（n）
  • 空間復(fù)雜度：O（n）

  這里時間復(fù)雜度是滿足了O（n），但是空間復(fù)雜度卻由于創(chuàng)建了哈希表而變成了O（n）

  3. 雙指針求解法
     兩個鏈表的長度是不一樣的，但是重疊部分是一樣的，也就是說后半部分是一樣的，那么就可以將長的鏈表的前半部分給裁剪了，然后將裁剪后的鏈表的起始節(jié)點(diǎn)作為第一個節(jié)，然后同時遍歷兩個鏈表進(jìn)行判斷是否相同，所以時間復(fù)雜度僅僅為O（n）
  • 時間復(fù)雜度：O（n）
  • 空間復(fù)雜度：O（1）

  這就是最符合題目的求解方法，從這道題也能看出來算法的重要性，他能夠提高空間和時間的效率

• 代碼：

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *nodeA = headA;
        ListNode *nodeB = headB;
        int lengthA = 0; 
        int lengthB = 0;
        while(headA) {
            lengthA++;
            headA = headA->next;
        }
        while(headB) {
            lengthB++;
            headB = headB->next;
        }
        if (lengthA >= lengthB) {
            int difference = lengthA - lengthB;
            for (int i = 0; i < difference; i++) {
                nodeA = nodeA->next;
            }
        } else {
            int difference = lengthB - lengthA;
            for (int i = 0; i < difference; i++) {
                nodeB = nodeB->next;
            }
        }
        while(nodeA!=nodeB) {
            nodeA = nodeA->next;
            nodeB = nodeB->next;
        }
        return nodeA;
    }