0%

LeetCode 160. Intersection of Two Linked Lists

Posted on Edited on In

题目

原题在此

解析

用两个指针同时开始遍历两个list, 在任意一个指针走到头时开始切换到另一个head继续遍历. 再两指针相等时退出循环. 此时如果两指针不为空则停在了交点处, 否则代表两个list没有交点.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *foo, ListNode *bar) {
        ListNode *a = foo, *b = bar;
        while(a != b) {
            a = a ? a->next : bar;
            b = b ? b->next : foo;
        }
        return a;
    }
};