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

// 获取链表长度
int getLensOfList(ListNode* head) {
	int len = 0;
	while (head != nullptr) {
		head = head->next;
		len++;
	}
	return len;
}

// 将head向后移动num个节点
ListNode* moveNode(ListNode** head, int num) {
	for (int i = 0; i < num; i++) {
		*head = (*head)->next;
	}
	return *head;
}

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
			// 空处理
			if (pHead1 == nullptr || pHead2 == nullptr) {
				return nullptr;
			}

			// 标记位 为0即为pHead1长反则pHead2长
			int flag;
			//k 获取len1 len2长度
			int len1 = getLensOfList(pHead1);
			int len2 = getLensOfList(pHead2);
			if (len1 > len2) {
				flag = 0;
			}
			else {
				flag = 1;
			}

			// 计算差值
			int diffOfLen = abs(len1 - len2);

			// 将较长的链表移动相差个数个节点
			if (flag == 0) {
				moveNode(&pHead1, diffOfLen);
			}
			else {
				moveNode(&pHead2, diffOfLen);
			}

			// 一起向后走若同时走到尾则没有相交
			while (pHead1 != nullptr || pHead2 != nullptr) {
				// 若两节点相等则为相等节点
				if (pHead1 == pHead2) {
					return pHead1;
				}
				pHead1 = pHead1->next;
				pHead2 = pHead2->next;
			}
			return nullptr;
    }
};