LeetCode 160. 相交链表 | C语言版_相交链表 leetcode c语言

LeetCode 160. 相交链表

题目描述

题目地址：160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

解题思路

思路一：使用双指针从左向右遍历

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //使用双指针
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;

    int lenA=0,lenB=0;
    //计算链表A的长度
    while(curA!=NULL){
        lenA++;
        curA=curA->next;
    }

    //计算链表B的长度
    while(curB!=NULL){
        lenB++;
        curB=curB->next;
    }

    curA=headA;
    curB=headB;

    //求出两个链表长度的差值，然后让长链表头指针向后移动到和短链表头指针相同的位置
    if(lenA>lenB){
        int gap=lenA-lenB;
        while(gap--){
            curA=curA->next;
        }
    }else{
        int gap=lenB-lenA;
        while(gap--){
            curB=curB->next;
        }
    }

    //curA，curB从同一位置向后遍历，直到遇到curA，curB相同时，即为交点
    while(curA!=NULL && curB!=NULL){
        if(curA==curB){
            return curA;
            //return curB;
        }
        curA=curA->next;
        curB=curB->next;
    }
    return NULL;

}
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
48
49
50
51
52
53

运行结果

参考文章：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/811955/dai-ma-sui-xiang-lu-160-xiang-jiao-lian-wxkmq/?q=%E4%BB%A3%E7%A0%81%E9%9A%8F%E6%83%B3%E5%BD%95&orderBy=most_relevant

思路二：减少遍历节点数

代码实现

在这里插入代码片
1

运行结果

参考文章：