题目

编写一个程序，找到两个单链表相交的起始节点
注意：

  • 如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路

架设存在两个链表 headA headB。定义两个指针 a b分别对应headA headB, 循环a b 直至到达链表的尾部，然后将a指向headB、将b指向headA ,继续循环直至出现a==b的情况，或者任意一个链表到达终点。

代码

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
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *a = headA;
    struct ListNode *b = headB;
    int aDone =0;
    int bDone =0;
    while(1)
    {
        if(a == b) {
            return a;
        }
        if(a && a->next) {
            a =  a->next;
        } else {
            if(aDone != 1) {
               a = headB;
               aDone = 1; 
            } else {
                break;
            }
            
        } 
        
        if(b && b->next )
        {
            b = b->next;
        } else {
            if(bDone != 1) {
                b = headA;
                bDone =1;
            } else {
                break;
            }
            
        }
        
    }
    return NULL;
    
   
}