链表#简单#相交链表

前文

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

如两个链表在节点c1开始相交：

a1->b1->c1->c2->c3
a2->b2->c1->c2->c3
// 则返回c1，两链表从c1开始相交

/**
 * 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) {
        
    }
};

正文

要点：

• struct的语法
• C++11的using 别名 = 类型;等价于C++03的typedef

解法1

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		if (headA == nullptr || headB == nullptr)
			return NULL;
		auto headB2 = headB;
		while(headA != nullptr) {
			while(headB != nullptr) {
				if (headA == headB)
					return headA;
				headB = headB->next;
			}
			headB = headB2;
			headA = headA->next;
		}
		return NULL;
    }
};

using Node = struct ListNode;
int main() {
	Node a1(1), b1(10), a2(2), b2(20), c1(8), c2(5), c3(3);
	a1.next = nullptr;
	a2.next = &b2;
	b1.next = &c1;
	b2.next = &c1;
	c1.next = &c2;
	c2.next = &c3;
	c3.next = nullptr;
	auto head1 = &a1;
	auto head2 = &a2;
	Solution so;
	cout << so.getIntersectionNode(head1, head2) << endl;
}

首先检查是否为空，为空直接返回NULL，接着遍历节点，查看哪两个节点相等，最后都没有则返回NULL。