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

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

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

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

一 单链表的基本使用

1. 数据结构

单链表中成员的一般包括节点内容和下一个节点的地址,这里用一个int代表节点的内容。为了在后面的代码中更好地看出程序的逻辑,这里没有自定义构造函数。

class node
{
public:
	int data;
	node *next;
};

2. 遍历链表

单链表中每个成员只有一个指针,于是只能从头节点一直遍历到尾节点,在遍历的过程可以统计链表的长度或打印链表的内容,如以下函数所示。

void print(node *head)
{
	for(node* p = head; p != NULL; p = p->next)
		printf("%d ", p->data);
	printf("\n");
}

int getLength(node *head)
{
	int len = 0;
	while (head != NULL) head = head->next, len++;
	return len;
}

3. 插入元素

在链表中插入元素有不同的插入方式,先考虑一个最简单的插入,就是在链表前面插入元素。

void insertBegin(node *&head, int val)
{
	node *newNode = new node();
	newNode->data = val, newNode->next = head;
	head = newNode;
}

还有一种相对应的方法是在链表末尾插入元素,需要遍历到末尾节点再进行插入,同时需要讨论原本的链表是否为空。

在链表的处理过程中,判断链表为空是经常需要进行的工作,这需要比较严谨的算法思考过程,稍有疏忽程序就会有潜在的bug,导致运行时出错。

void insertEnd(node *&head, int val)
{
	node *newNode = new node();
	newNode->data = val, newNode->next = NULL;
	if (head == NULL)
		head = newNode;
	else
	{
		node *p = head;
		while (p->next != NULL) p = p->next;
		p->next = newNode;
	}
}

考虑一种在有序链表中插入元素的操作。这里需要先遍历到待插入的位置的节点上,然后根据待插入的地方是链表末尾、头部还是中间部分不同情况进行不同操作。

void insert(node *&head, int num)
{
	node *p1 = head, *p2 = NULL;
	while (p1->data < num && p1->next != NULL)
		p2 = p1, p1 = p1->next;

	node *p = new node();
	p->data = num;
	if (p1->data < num)
		p1->next = p, p->next = NULL;
	else if (p1 == head)
		p->next = p1, head = p;
	else
		p2->next = p, p->next = p1;
}

有时会给定一个节点p的指针,要求我们在p之前或之后一个元素。

在p的后面插入元素是比较简单的,可以直接进行next指针的修改。

但是在前面插入元素比较困难,因为从指针p中无法得到前一个节点的指针,于是也就不能修改前面节点的next指针来插入元素。但是可以做一个简单的处理,首先把待插入的元素复制到节点p之上,然后问题就转化为在节点p之后插入一个新的节点,这个节点的值是原本p的值,而这种在后面插入元素是我们可以直接进行的。于是问题得解。

4. 删除元素

这里实现的是在链表中删除某个元素。首先遍历链表找到该元素的位置,然后再分该位置是链表头部还是中间部分不同情况进行处理。注意删除元素时要释放原有元素占用的内存,否则会造成内存泄露。

void remove(node *&head, int num)
{
	node *p1 = head, *p2 = NULL;
	while(p1->data != num && p1->next != NULL)
		p2 = p1, p1 = p1->next;
	if (p1->data != num)
		printf("%d NOT found\n", num);
	else
	{
		if (p1 == head)
		{
			head = p1->next;	delete p1;
		}
		else
		{
			p2->next = p1->next;	delete p1;
		}
	}
}

面试中经常要求删除给定节点指针p指向的那个节点,一般p指向的不是末尾节点。

在单链表的删除操作中,我们需要知道删除的节点的前一个节点的指针,然后才能修改它的next指针的值达到删除节点的目的。

但是这里我们只有p节点指针,根据单链表无法得到其上一个节点的指针,但是我们可以知道它的下一个节点q的指针,于是我们可以节点q的内容全部复制到p上,然后把节点q删除掉。这样效果上等价于直接删除p,但是删除q是比较简单的事情,因为我们已经知道它的前一个节点p了。

5. 排序

在数组上有许多经典的排序方法,理论上它们都可以在链表上相应地实现。但由于链表不能对其上的元素进行随机访问,导致许多经典的排序算法在链表上的效率并不高。

下面我们实现一个经典的O(n^2)的冒泡排序算法:

void bubbleSort(node *head)
{
	int len = 0;
	for (node *p = head; p != NULL; p = p->next) len++;

	for (int i = 1; i < len; i++)
	{
		node *p = head;
		for(int j = 0; j < len - i; j++, p = p->next)
			if (p->data > p->next->data)
			{
				int tem = p->data; 
				p->data = p->next->data; 
				p->next->data = tem;
			}
	}
}

归并排序是链表排序一种很好的方法,它不但保留了原本O(nlgn)的时间复杂度,而且普通数组归并时需要额外O(n)的空间在这里也变为只需要O(1)的空间。

归并排序首先要解决的归并两个已经有序的链表为一个链表,由以下代码实现。这里是一个非递归的实现,首先创建了一个辅助节点,最后再把这个节点删除。

node* merge(node *l, node *r)
{
	if (l == NULL) return r;
	else if(r == NULL) return l;

	node *result= new node(), *p = result;
	while (l != NULL && r != NULL)
		if (l->data < r->data)
			result->next = l, result = l, l = l->next;
		else
			result->next = r, result = r, r = r->next;
	if (l != NULL)	result->next = l;
	if (r != NULL)	result->next = r;

	result = p->next;
	delete p;
	return result;
}

由于链表不能随机读取,于是把链表分成两个部分的工作比数组要复杂一些。这里是使用了快慢指针的方法,快慢两个指针初始化为链表头部,快指针移动的步长为2,慢指针的步长为1,于是快指针到达链表尾部的时候,慢指针刚好到达中间,于是可以根据这点把链表分为两个部分。

注意要把左边链表的最后一个节点的next值设为空,否则就没有达到切成两个链表的效果。

void split(node *head, node *&l, node *&r)
{
	if (head == NULL || head->next == NULL)
	{
		l = head, r = NULL;		return;
	}

	node *slow = head, *fast = head->next;
	while (fast != NULL)
	{
		fast = fast->next;
		if (fast != NULL)
			fast = fast->next, slow = slow->next;
	}
	l = head, r = slow->next;
	slow->next = NULL;
}

下面就是归并排序的主函数。把链表切成左右两部分,递归地对两部分排好序,然后再归并起来得到最终排好序的链表。

void mergeSort(node *&head)
{
	if (head == NULL || head->next == NULL) return;
	node *l, *r;
	split(head, l, r);
	mergeSort(l); mergeSort(r); 
	head = merge(l, r);
}
上一篇: 下一篇:

我的博客

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

站内搜索

最新评论