LeetCode 160. Intersection of Two Linked Lists

題目

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

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.

翻譯

寫一支程式找出兩個連結陣列的第一個交集的節點。

注意：

• 如果兩個連結陣列沒有交集，回傳null
• 連結陣列必須保持他們的原始結構
• 可以假設不會出現迴圈連結陣列
• 程式只能在O(n)的時間跑完而且只能使用O(1)的空間

思路

先判斷A跟B哪個連結陣列長度比較長，接著移除較長那邊前面的節點，接下來就兩兩節點比較是否相等。

解題

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    // 判斷headA, headB 哪個比較長
    var diff = getDiff(headA, headB);

    // headA比較長，跳過前面多出的部分
    if(diff > 0){
        while(diff > 0){
            headA = headA.next;
            diff--;
        }
    } else {
        // headB比較長，跳過前面多出的部分
         while(diff < 0){
            headB = headB.next;
            diff++;
        }       
    }

    // 毎個節點進行比較
    while(headA !=null){
        if(headA == headB){
            return headA;
        }    
        headA = headA.next;
        headB = headB.next;
    }

    return null;


    // 取得兩個linked list長度差異 
    function getDiff(nodeA,nodeB){
        var aLength = 0;
        var bLength = 0;

        while(nodeA != null ){
            aLength++;
            nodeA = nodeA.next;
        }
        while(nodeB != null ){
            bLength++;
            nodeB = nodeB.next;
        }

        return aLength - bLength;
    }
};