JZ36 两个链表的第一个公共结点

本文最后更新于：2022年4月9日 中午

image-20211008105823220

Solution

  • 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == nullptr || pHead2 == nullptr) return nullptr;
        ListNode* p1 = pHead1, *p2 = pHead2;
        while (p1 != p2) {
            p1 = (p1 != nullptr) ? p1->next : pHead2;
            p2 = (p2 != nullptr) ? p2->next : pHead1;
        }
        return p1;
    }
};
  • 暴力法
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
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == nullptr || pHead2 == nullptr) return nullptr;
        int l1 = 0, l2 = 0;
        ListNode* p1 = pHead1, *p2 = pHead2;
        while (p1) {
            l1++;
            p1 = p1->next;
        }
        while (p2) {
            l2++;
            p2 = p2->next;
        }
        
        p1 = pHead1, p2 = pHead2;
        if (l1 > l2) {
            int n = l1 - l2;
            while (n--) p1 = p1->next;
        } else {
            int n = l2 - l1;
            while (n--) p2 = p2->next;
        }
        
        ListNode* node = nullptr;
        while (p1 && p2) {
            if (p1->val == p2->val) {
                if (node == nullptr) node = p1;
            } else {
                node = nullptr;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return node;
    }
};