面试中常见的链表题汇总

Bertha 。 2022-08-06 00:23 176阅读 0赞

链表是我们在编程中常用的一种数据结构，并且结构简单，因此在面试中会经常出现考察链表的题目，下面我们来看看面试中常见的一些关于链表的题目。首先了解一下链表的数据结构如下：**注意**：在编写代码时一定要记住边界条件的判断，这样才能够体现思维的严谨性。

typedef struct ListNode
    {
    	int data;
    	ListNode* next;
    }ListNode;

**1、计算单链表中节点的个数。**

int GetListLength(ListNode* pHead)
    {
     	if(NULL==pHead)
    	{
    		return 0;
    	 }
    
    	 unsigned int nLength=0;
    	ListNode* p=pHead;
    
    	 while(p)
    	{
    		++nLength;
    
    		 p=p->next;
    	 }
    
    	 return nLength;
    }

**2、单链表的反转**

注意判断只有一个结点或者链表为空的情况，通过循环遍历交换相邻结点的next指针即可，时间复杂度为O(n)**。**

ListNode* ListReverse(ListNode* pHead)
    {
    	if(NULL==pHead||NULL==pHead->next)
    	{
    		 return pHead;
    	}
    
    	ListNode* p=pHead;
    	ListNode* q=p->next;
    	ListNode* r;
    	while(q)
    	{
    		r=p->next;
    		q->next=p;
    		p=q;
    		q=r;
    	}
    	pHead->next=NULL;
    	pHead=p;
    
    	return pHead;
    }

**3、查找单链表中倒数第k个结点**

本题目可以首先遍历一边链表计算出链表的长度n，然后遍历找到第n-k个结点。

我们还可以反过来思考，通过两个指针，p，q。p和q同时指向头结点，p指针先走k步，然后p和q一起走，这样p走完n-k步到达链表尾部，q走到第n-k个结点，即倒数第k个结点，时间复杂度小于O（n）注意：临界情况的判断。

ListNode* GetRkNode(ListNode* pHead,unsigned int k)
    {
    	 if(k==0||NULL==pHead)
    	{
    		 return NULL;
    	}
    	
    	ListNode* p=pHead;
    	ListNode* q=pHead;
    
    	 unsigned int i;
    	 while (q)
    	{
    		++i;
    
    		 if(i==k)
    		 {
    			break;
    		}
    
    		q=q->next;
    	 }
    
    	 if(i<k)
     	{
    		return NULL;
     	}
    
    	 while(q)
    	{
    		 p=p->next;
    		q=q->next;
     	}
    
    	 return p;
    }

**4、查找单链表中的中间结点**

本题还是采用两个指针的方式，第一个指针每次走2步，第二个指针每次走1步，当第一个指针到达链表尾部后，第二个指针刚好到达中间节点。

ListNode* GetMidNode(ListNode* pHead)
    {
    
    	if(NULL==pHead||NULL==pHead->next)
    	{
    		return pHead;
    	}
    
    	ListNode* p=pHead;
    	ListNode* q=pHead;
    
    	while (p)
    	{
    		p=p->next->next;
    		q=q->next;
    	}
    
    	return q;
    }

**5、从尾到头打印单链表**

从尾向前打印单链表，我们可以快速的想到使用栈的特性，先正向遍历加入栈，最后在取出来进行打印。

void RPrintfNode(ListNode* pHead)
    {
    	if(NULL==pHead)
    	{
    		return;
    	}
    	std::stack<int> stackNode;
    
    	while (pHead)
    	{
    		stackNode.push(pHead->data);
     		pHead=pHead->next;
    	}
    
    	 while(!stackNode.empty())
    	{
    		 int data=stackNode.top();
    
    		 printf("%d",data);
    		
    		stackNode.pop();
    	 }
    }

**6、已知两个单链表从小到大的顺序，把他们合并后依然有序（链表的归并排序）。**

首先注意临界条件的判断，只需遍历比较链表，直到有一个链表到达尾部，再把剩下不为空的节点加到新的链表尾部即可，注意要利用原始的空间。

ListNode* MergeList(ListNode* pHead1,ListNode* pHead2)
    {
    	if(NULL==pHead1)
    	{
    		return pHead2;
    	}
    	if(NULL==pHead2)
    	{
    		return pHead1;
    	}
    	if(NULL==pHead1&&NULL==pHead2)
    	{
    		return NULL;
    	}
    
    	ListNode* p=pHead1;
    	ListNode* q=pHead2;
    	ListNode* pNewNode=NULL;
    	ListNode* pHead;
    
    	while(p!=NULL&&q!=NULL)
    	{
    		if(p->data>q->data)
    		{
    
    			if(pNewNode==NULL)
    			{
    				pNewNode=q;
    				pHead=q;
    				q=q->next;
    			}
    			else
    			{
    				pNewNode->next=q;
    				pNewNode=q;
    				q=q->next;
    			}
    		}
    		else 
    		{
    			if(pNewNode==NULL)
    			{
    				pNewNode=p;
    				pHead=p;
    				p=p->next;
    			}
    			else
    			{
    				pNewNode->next=p;
    				pNewNode=p;
    				p=p->next;
    			}
    		}
    	}
    
    	if(p!=NULL)
    	{
    		pNewNode->next=p;
    	}
    	if(q!=NULL)
    	{
    		pNewNode->next=q;
    	}
    
    	return pHead;
    }

**7、判断一个链表中是否存在环**

如果链表中存在环，则可以采用两个指针第一个每次走1不，第二个每次走2步，如果两个指针相遇，则肯定存在环。

bool IsExitLoop(ListNode* pHead)
    {
    	if(NULL==pHead)
    	{
    		return false;
    	}
    
    	ListNode* p=pHead;
    	ListNode* q=pHead;
    
    	while(p!=NULL&&q->next!=NULL)
    	{
    		p=p->next;
    		q=q->next->next;
    
    		if(p==q)
    		{
    			return true;
    		}
    	}
    
    	return false;
    }

**8、判断两个单链表是否相交;**

注意：如果两个链表相交，则两个链表的尾节点肯定相同，因此可以判断两个链表的尾部节点是否相同即可。

bool IsIntersect(ListNode* pHead1,ListNode* pHead2)
    {
    	if(NULL==pHead1||NULL==pHead2)
    	{
    		return false;
    	}
    
    	while (pHead1->next!=NULL)
    	{
    		pHead1=pHead1->next;
    	}
    
    	while(pHead2->next!=NULL)
    	{
    		pHead2=pHead2->next;
    	}
    
    	if(pHead1==pHead2)
    	{
    		return true;
    	}
    
    	return false;
    }

**9、求单链表相交的第一个交点;**

求单链表相交的一个交点，我们主要不知道是两个链表的长度，假设链表1的长度是length1，链表2的长度是length2，如果length1>length2,则如果让链表1先走length1-length2步，再让链表2从头结点一起开始走，则他们如果相等的话，则为相遇的节点。

ListNode* GetFirstIntersect(ListNode* pHead1,ListNode* pHead2)
    {
    	if(pHead1==NULL||pHead2==NULL)
    	{
    		return NULL;
    	}
    
    	unsigned int length1=0,length2=0;
    
    	ListNode* p=pHead1;
    	ListNode* q=pHead2;
    
    	while(p->next!=NULL)
    	{
    		p=p->next;
    		++length1;
    	}
    
    	while(q->next!=NULL)
    	{
    		q=q->next;
    		++length2;
    	}
    
    	if(p!=q)
    	{
    		return NULL;
    	}
    	p=pHead1;
    	q=pHead2;
    
    	if(length1>length2)
    	{
    		p=pHead1;
    
    		unsigned int k=length1-length2;
    
    		while(k)
    		{
    			p=p->next;
    			k--;
    		}
    	}
    	else
    	{
    		q=pHead2;
    
    		unsigned int k=length2-length1;
    
    		while(k)
    		{
    			q=q->next;
    			k--;
    		}
    	}
    
    	while(p==q)
    	{
    		p=p->next;
    		q=q->next;
    
    		return p;
    	}
    
    	return NULL;
    }

**10、已知单链表中存在环,求进入环的第一个节点**

单链表中存在的环我们可以通过上面介绍的方法来进行判断，设两个指针，一个慢指针p，一个快指针q，p每次走1步，q每次走2步，当p和q相遇时说明链表中存在环。

记录相遇的节点pNode，然后从链表头指针和pNode，每次走一步，两指针相遇时即为环的入口点。

ListNode* GetFirstNodeOfLoop(ListNode* pHead)
    {
    	if(NULL==pHead)
    	{
    		return NULL;
    	}
    
    	ListNode* p=pHead;
    	ListNode* q=pHead;
    
    	while(p!=NULL&&q->next!=NULL)
    	{
    		p=p->next;
    		q=q->next->next;
    
    		if(p==q)
    		{
    			break;
    		}
    	}
    
    	if(q==NULL||q->next==NULL)
    	{
    		return NULL;
    	}
    
    	p=pHead;
    
    	while(p!=q)
    	{
    		p=p->next;
    		q=q->next;
    	}
    
    	return p;
    }

第10题的证明如下：

当pfast若与pslow相遇时，pslow肯定没有走遍历完链表，而pfast已经在环内循环了n圈(1<=n)。假设pslow走了s步，则pfast走了2s步（pfast步数还等于s 加上在环上多转的n圈），设环长为r，则：

2s = s + nr 　s= nr  
设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。

a + x = nr 　则 　a + x = (n – 1)r +r = (n-1)r + L - a 　　a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

总结：链表是面试中常出现的面试题，注重基础知识的培养，并能够熟知一些常见的题目，定会熟能生巧。由于时间关系，上述代码并没有做测试用例，如有错误望读者指正，并多多包含。