Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 面试 » ,

C++单链表面试问题(2)

链表是程序设计的基本数据结构,也是程序员笔试面试中经常出现的问题。虽然链表在实际中应用不是太广泛,但是它在一些细节的处理上能够很好地体现出一个程序员的编程技巧和思维能力。
这里总结了一些面试中常见的单链表内容,具体分为两个部分,本文主要介绍单链表的综合使用问题。

  1. C++单链表面试问题(1):单链表的基本使用
  2. C++单链表面试问题(2):单链表的综合使用

二 单链表的综合使用

1. 查找元素

因为链表不能随机读取,所以一般索引元素时需要先遍历链表一次得到链表的长度,然后第二次遍历时再读取指定的元素。这里讲到一种使用两个指针实现只需遍历一次链表的技巧。

仅遍历一次链表找出链表的中间元素。

这里使用快慢指针的技巧,前面在归并排序的时候已经使用了这个技巧,这里的思想是一样的。快慢两个指针都从链表头开始遍历,快指针的步长是2,慢指针的步长是1,即快指针走的速度是慢指针的两倍。于是快指针到达链表末尾的时候慢指针刚好到达中间位置,于是可以得到中间元素的值。

node* findMiddle(node *head)
{
	if (head == NULL || head->next == NULL) return head;

	node *p = head, *q = head->next;
	while (q != NULL)
	{
		q = q->next;
		if (q != NULL) p = p->next, q = q->next;
	}
	return p;
}

仅遍历一次链表找出倒数第k个元素,倒数第0个表示最后一个。

这里是让一个指针从头开始,一个指针从第k个元素开始,两个指针速度一样,到前面指针到达末尾的时候,后面指针刚好到达倒数第k个元素的位置。

node* findLastK(node* head, int k)
{
	node *p = head, *q = head;
	for (int i = 0; i < k; i++)
		if (q->next == NULL)	return NULL; //长度过短
		else	q = q->next;			
	while (q->next != NULL) q = q->next, p = p->next;
	return p;
}

2. 链表反转

反转一个链表比较简单,只需要把原来每一个指针的指向反转过来即可。

node* reverse1(node *head)
{
    if (head == NULL || head->next == NULL) return head;
 
    node *pre = NULL;
    while (head != NULL)
    {
        node *nxt = head->next;
        head->next = pre;
        pre = head, head = nxt;
    }
    return pre;
}

这里再提供一个递归的版本。

node* reverse2(node *head)
{
	if (head == NULL || head->next == NULL) return head;

	node* rhead = reverse2(head->next);
	head->next->next = head, head->next = NULL;
	return rhead;	
}

3. 单链表与环

给定一个单链表,判断是否有环?环的起点?环的长度?

使用快慢指针方法,快指针的速度是慢指针的两倍,当链表中有环存在时,链表成6字形状,于是快指针迟早会追上慢指针的;当链表中没有环时,快指针最终会走到链表的末尾节点,于是可以根据这两点判断链表中是否有环。

当有环存在时,快慢指针会在环内相遇,记录下这个相遇的位置。让快慢指针同时从相遇位置开始走,则他们会绕着环走,由于快指针的速度是慢指针的2倍,于是第二次相遇时经过的迭代步数即为环的长度。

下面求环的起点。让两个指针一个从起点开始,一个从初次相遇的位置开始,以相同的速度前进,则他们第一次相遇的地方即为环的入口地点。证明如下,假设起点到环的入口长度为a,入口到初次相遇的地方长度为b,则初次相遇时,慢指针走了a+b,快指针走了2*(a+b),假设快指针当时转了n圈、环的长度为r,则2*(a+b)=(a+b)+n*r,即a+b = nr, a = (n-1)r + r-b,当从起点开始的指针走了a到达入口时,从相遇点开始的指针走了n-1圈和r-b的长度,刚好也到达入口。

void findRing(node *head)
{
	node *fast = head, *slow = head;
	while (fast != NULL)
	{
		fast = fast->next;
		if (fast->next != NULL)
			fast = fast->next, slow = slow->next;
		if (fast == slow) break;
	}
	if (fast == NULL) 	printf("No ring\n");
	else
	{
		node *p1 = fast, *p2 = fast;
		int len = 0;
		while (1)
		{
			len++, p1 = p1->next->next, p2 = p2->next;
			if (p1 == p2)
			{
				printf("Ring found, length: %d\n", len); break;
			}
		}
		slow = head;
		while (slow != fast) slow = slow->next, fast = fast->next;
		printf("Ring Entry: %d\n", fast->data);
	}
}

4. 链表相交

判断两个无环链表是否相交,如果有,求相交点。

当两个无环链表相交时,类似于两根铁轨并轨,其最终会停止于一个共同的节点,于是可以通过判断两个链表的末尾节点是否相同判断两个无环链表是否相交。

当链表相交时,先求得链表的长度为len1和len2,然后让较长的链表的指针先走|len1-len2|步的距离,目的是让两个链表的指针站在同一个起跑线上,然后两个指针一起遍历,首次出现两个节点一样的地方就是链表相交的地方。

判断两个可能有环的链表是否相交,如果有,求相交点

首先可以使用上述方法判断链表中是否存在环。如果两个都没环,使用以上方法进行。如果一个有环一个无环,则肯定不会相交。

剩下两个都有环的情况。首先在一个链表上使用快慢指针的方法得到一个相遇点,然后判断该相遇点是否在另一个另一个链表上(也可以使用快慢指针的方法),然后即可判断是否相交。如果相交了,则相交点可能在环外也可能在环上。如果在环外,可以使用无环链表相交的方法求得相交点。否则,任意一个链表在环上的入口节点都可以作为相交点。

上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论