Leetcode160.相交链表（C语言）_相交链表 leetcode c语言

Leetcode160.相交链表（C语言）

数据结构-链表：算法与数据结构参考

题目：
例如以下示例中 A 和 B 两个链表相交于 c1：

若存在则返回c1,如果不存在交点则返回 null。
要求时间复杂度为 O(N)，空间复杂度为 O(1)。

思路：
使得A，B两个链表剩下的长度相同，再进行逐个比较找出交点。
A,B各自长度未知，重点在于长度的处理

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL || headB==NULL) return NULL;
    
    int lena,lenb;
    struct ListNode *p=headA;
    struct ListNode *q=headB;
    
    for(lena=0;p=p->next;lena++);
    for(lenb=0;q=q->next;lenb++);
    int diff=lena-lenb;						//计算两个链表的长度差
    
    while(diff>0){
        headA=headA->next;
        diff--;
    }
    
    while(diff<0){
        headB=headB->next;
        diff++;
    } 												//定位两个链表的节点，使余下链表长度相等
    
    while(headA!=headB){
        headA=headA->next;
        headB=headB->next;
    }
    
    return headA;
}
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