欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Leetcde每日一题:160.intersection-of-two-linked-lists(相交链表)

程序员文章站 2022-03-12 09:17:27
思路:这道题咋一看觉得挺容易,就是遍历两个链表,然后若两个指针值相同(指向同一节点),那么改结点就是相交点!但是,题目给出的两个链表长度是不一致的,所以我们得把不一致的链表转化成一致的链表;struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};//假定链表A长于链表B,lenMin为链表B的长度ListNode *Check(ListNode *headA, int le.....

Leetcde每日一题:160.intersection-of-two-linked-lists(相交链表)
Leetcde每日一题:160.intersection-of-two-linked-lists(相交链表)
思路:这道题咋一看觉得挺容易,就是遍历两个链表,然后若两个指针值相同(指向同一节点),那么改结点就是相交点!但是,题目给出的两个链表长度是不一致的,所以我们得把不一致的链表转化成一致的链表;
Leetcde每日一题:160.intersection-of-two-linked-lists(相交链表)
Leetcde每日一题:160.intersection-of-two-linked-lists(相交链表)

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

//假定链表A长于链表B,lenMin为链表B的长度
ListNode *Check(ListNode *headA, int lenA, ListNode *headB, int lenB)
{
	int dis = lenA - lenB;
	//让长链表先走,走到长度与短链表一致;
	while (headA != NULL && dis--)
	{
		headA = headA->next;
	}
	//然后两个链表同时遍历,如果指针值相同,说明该指针指向的结点就是插入节点!
	while (headA != NULL && headB != NULL)
	{
		if (headA == headB)
		{
			ListNode *result = headB;
			return result;
		}
		headA = headA->next;
		headB = headB->next;
	}
	return NULL;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
	//两个链表都遍历一次,找到短链表,从而确定长链表改从何处开始判断
	ListNode *head1 = headA;
	ListNode *head2 = headB;
	int lenA = 0;
	int lenB = 0;
	while (head1 != NULL)
	{
		lenA++;
		head1 = head1->next;
	}
	while (head2 != NULL)
	{
		lenB++;
		head2 = head2->next;
	}
	if (lenA > lenB)
	{
		return Check(headA, lenA, headB, lenB);
	}
	else
	{
		return Check(headB, lenB, headA, lenA);
	}
}

本文地址:https://blog.csdn.net/wyll19980812/article/details/107134489