[LeetCode從零單刷]Intersection of Two Linked Lists

[LeetCode從零單刷]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

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.

解答：

需要的是常量級別的空間，而且時間是遍歷的時間（可以常數次的多次遍歷）。

因為是單鏈表，所以沒辦法從尾部開始回搜到第一個不相同的節點。那能不能從頭部開始搜到第一個相同的節點？

好像不行，因為鏈表的長度各不相同。如果是長度相同的鏈表就可以了。我們截掉更長的鏈表的頭幾個多余元素。

如果我可以知道兩者的鏈表長度，長度通過遍歷鏈表得到。

 

/**
 * 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) {
        ListNode* ha = headA;
        ListNode* hb = headB;
        int lenA = 0;
        int lenB = 0;
        
        while(ha != NULL) {ha = ha->next; lenA++;}
        while(hb != NULL) {hb = hb->next; lenB++;}
        ha = headA;
        hb = headB;
        
        if(lenA > lenB) {
            int diff = lenA - lenB;
            while(diff--)   ha = ha->next;
        }
        
        if(lenB > lenA) {
            int diff = lenB - lenA;
            while(diff--)   hb = hb->next;
        }
        
        while(ha) {
            if(ha == hb)    return ha;
            ha = ha->next;
            hb = hb->next;
        }
        return NULL;
    }
};