目录

题目描述

问题分析

代码及结果

时间复杂度和空间复杂度分析

---

题目描述

给定两个单链表，编写程序找出两个链表的公共结点。

！！！图中没有画出Head2的头结点，大家注意一下

 在这里，大家需要注意的是两个链表的公共结点不是指数据域相同的结点，而是指地址相同的结点。

问题分析

通过上图，我们可以得到如果两个链表有公共结点，那么从公共结点开始，两个链表后面的结节都是相同的（红色框）；从这一点出发，我们可以先得到两个链表的长度（length1和length2），让长的链表先走两个链表长度相减的那一段结点(蓝色框)，然后我们可以认为两个链表的长度是相等的（绿色框+红色框）。值得注意的是，因为我在初始化链表是带有了头结点，所以我在让长链表走之前，让两个链表都走了一个头结点（LinkList s1 = head1->next;LinkList s2 = head2->next;）。当长链表走完了（length1-length2）后，再让两个链表同步走，若是遇到公共结点，则返回该结点，否则返回NULL。

代码及结果

 .h头文件（声明函数及定义结构体）

#pragma once

typedef  int ElemType;

typedef struct NodeList
{
	ElemType data;//数据域
	struct NodeList *next;//指针域
}NodeList,*LinkList;

int InitNode(LinkList head);//初始化链表（带有头结点），失败返回0

int InsertHead(LinkList head, ElemType value);//在链表头部插入数据

//根据所给的value值查找链表中为value的结点地址，若链表中没有该结点返回NULL
LinkList GetNode(LinkList head, ElemType value);

int Empty(LinkList head);//判断链表是否为空，空链表返回1

int GetLenght(LinkList head);//得到链表的长度

//判断两个链表中是否有公共结点，如果有则返回该结点，如果没有则返回NULL
LinkList CommomNode(LinkList head1, LinkList head2);

void Destory(LinkList head);//销毁链表，回收空间

void Show(LinkList head);//打印输出该链表

.c文件（定义函数）

#include"CommonNode_TwoLinkList.h"
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>

int InitNode(LinkList head)
{
	assert(head != NULL);

	if (head == NULL)
	{
		printf("ÏnitNode :: HeadNode is NULL!\n");
	}
	head->next = NULL;//带有头结点
	return 1;
}
int InsertHead(LinkList head, ElemType value)
{
	assert(head != NULL);
	if (head == NULL)
	{
		printf("InsertHead :: HeadNode is NULL!\n");
	}

	LinkList s = (LinkList)malloc(sizeof(NodeList));//申请空间，为插入的链表结点
	if (s == NULL)
	{
		printf("InsertHead ::ApplyNode Failed!\n");
		return 0;
	}

	s->data = value;
	s->next = head->next;//两个顺序不能颠倒
	head->next = s;

	return 1;
}

LinkList GetNode(LinkList head, ElemType value)
{
	assert(head != NULL);
	if (head == NULL)
	{
		printf("GetNode :: HeadNode is NULL!\n");
	}

	LinkList s = head;
	while (s->next != NULL)
	{
		s = s->next;
		if (s->data == value)
		{
			return s;
		}
	}

	return NULL;
}

int Empty(LinkList head)
{
	assert(head != NULL);
	
	return head == NULL || head->next == NULL;
}

int GetLenght(LinkList head)
{
	assert(head != NULL);
	if (head == NULL)
	{
		printf("GetLenght :: HeadNode is NULL!\n");
	}

	int length = 0;
	LinkList s = head;
	while (s->next != NULL)
	{
		s = s->next;
		length++;
	}
	return length;
}

LinkList CommomNode(LinkList head1, LinkList head2)
{
	assert(head1 != NULL && head2 != NULL);
	if (head1 == NULL || head2 == NULL)
	{
		printf("CommomNode :: HeadNode is NULL!\n");
	}
	int length1 = GetLenght(head1);
	int length2 = GetLenght(head2);

	LinkList s1 = head1->next;
	LinkList s2 = head2->next;

	int length = length1 - length2;
	//让较长的链表先走，知道他们两个长度相等为止
	if (length > 0)
	{
		while (length)
		{
			s1 = s1->next;
			length--;
		}
	}
	else
	{		
		while (length)
		{
			s2 = s2->next;
			length--;
		}
	}

	while (s1->next != NULL)//经过上面的步骤，两个链表的长度已经相等，只需要判断一个链表是否为空即可
	{
		if (s1 == s2)
		{
			return s1;
		}
		s1 = s1->next;
		s2 = s2->next;
	}

	return NULL;
	
}
void Destory(LinkList head)
{
	assert(head != NULL);

	free(head);
	head = NULL;
}

void Show(LinkList head)
{
	assert(head != NULL);

	LinkList s = head;
	printf("Head");
	while (s->next != NULL)
	{
		s = s->next;
		printf("--> %d ",s->data);
	}

	printf("-->NULL\n");
}

main.c文件（测试）

#include"CommonNode_TwoLinkList.h"
#include<assert.h>
#include<stdio.h>

int main()
{
	NodeList Head1;
	NodeList Head2;

	InitNode(&Head1);
	InitNode(&Head2);

	InsertHead(&Head1, 9);
	InsertHead(&Head1, 8);
	InsertHead(&Head1, 7);
	InsertHead(&Head1, 6);
	InsertHead(&Head1, 5);
	InsertHead(&Head1, 3);

	LinkList s = GetNode(&Head1, 7);

	InsertHead(&Head2, 13);
	InsertHead(&Head2, 12);
	InsertHead(&Head2, 11);
	InsertHead(&Head2, 10);

	printf("Show Head1: ");
	Show(&Head1);
	printf("Show Head2: ");
	Show(&Head2);

 	LinkList p = CommomNode(&Head1, &Head2);
	if (p == NULL)
	{
		printf("Don't  Having CommonNode!\n");
	}
	else
	{
		printf("Having CommonNode!\n");
	}

	return 0;
}

 vs2019测试结果

时间复杂度和空间复杂度分析

     时间复杂度：O(length1+length2)，（计算两个链表的长度）

     空间复杂度：O(1)。(没有用到多余空间)