160. 相交链表

Solution1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        std::set<ListNode*> node_set;
        while(headA){
            node_set.insert(headA);
            headA = headA->next;
        }
        while(headB){
            if(node_set.find(headB)!=node_set.end()){
                return headB;
            }
            headB = headB->next;
        }
        return NULL;
    }
};

思路：

这种思路很简单。就是先将链表A的每个元素存入set中，在链表B的元素逐个去set中查找。找到就返回。
缺点：
使用了O(n)的空间。

Solution2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//获得链表的长度。
int get_list_length(ListNode * head){
    int len = 0;
    while(head){
        head = head->next;
        len++;
    }
    return len;
}
//将长的链表移动多余的步数；以致两个链表到了相等的长度。
ListNode* forward_long_list(int long_len, int short_len, ListNode* head){
    int step = long_len-short_len;
    while(head && step){
        head = head->next;
        step--;
    }
    return head;
}

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int headA_len = get_list_length(headA);
        int headB_len = get_list_length(headB);
        //先移动较长的链表至两个链表的长度相等。
        if(headA_len>headB_len){
            headA = forward_long_list(headA_len,headB_len,headA);
        }else{
            headB = forward_long_list(headB_len,headA_len,headB);
        }
        //再同时开始移动。如果这两个结点相等了，就找到了
        while(headA && headB){
            if(headA == headB){
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        return NULL;
    }
};

思路：

由于后面的结点是两个链表共享的，所以链表在相交结点之前有可能长度不相等。

我们先将长的链表移动到与短链表相同的长度，然后两个链表同时移动，当两个结点变得相同时，就得到了相同结点。