面试题 02.07. 链表相交

面试题 02.07. 链表相交 - 力扣（LeetCode）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

ps：链表相交并不是说两个链表中的元素相等而已，而是指链表交点的指针（就是说两个链表中，存在某一元素存储的地址是一致的），并且从这个地址之后的所有元素都相等。

思路

暴力解法：（c语言实现）

​ 个人第一次解的时候使用的方法，使用两个循环，查找地址相同的两个节点，并且指向的下一个地址也相同，则就是两个链表的交点。

巧妙解法：（C++实现）

  • 得出两个链表长度
  • 计算链表长度差gap（C++中可以用swap（a，b），快速交换a和b的值）
  • 长链表指针先移动gap位，使得两个链表尾部对齐
  • 开始同时遍历长链表和短链表，找到相同的地址节点后返回

这么做的话也就是说，两个链表要是相交的话，一定从短链表中的元素开始的。

c语言代码如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    typedef struct ListNode ListNode;
    ListNode* B = (ListNode*)malloc(sizeof(ListNode));
    B->next = headB;
    ListNode* cur = B;
    ListNode* ans = NULL;
    int n = 0;
    while(headA){
        while(cur){
            if((cur->next == headA->next) && (cur == headA)){//是接下来的指向的位置相等，不是存储的数字相等
                return cur;
            }
            cur = cur->next;
        }
        headA = headA->next;
        cur = B;
    }
    return ans;
}

C++实现如下：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode* curA = headA;
        ListNode* curB = headB;
        while(curA != NULL){
            lenA++;
            curA = curA->next;
        }   
        while(curB != NULL){
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        if(lenB>lenA){
            swap(lenA,lenB);//快速交换两个元素的值
            swap(curA,curB);
        }
        int gap = lenA - lenB;
        while(gap){
            gap--;
            curA = curA->next;
        }
        while(curA != NULL){
            if(curA==curB){
                return curA;
            }
            curA=curA->next;
            curB=curB->next;
        }
        return NULL;
    }
};