面试中的链表问题总结

  链表是比较简单的数据结构，但是涉及到指针的使用，一般情况下链表的面试题代码都不长，但是可以考察应试者的编程基本功，这类题目在面试中经常出现。

面试题1：求链表中倒数第k个节点

题目：输入一个链表(不带空头节点)，输出该链表倒数第k个数，链表结点定义如下:

struct ListNode{
    int val;
    ListNode* next;
};

很容易就想到这肯定是一个O(n)的算法，如何才能得到倒数第k个节点呢？考虑用两个指针(p_1,p_2)，先让指针(p_2)向前走(k)步，然后两个指针同步走，直到(p_2)走到NULL时，这时候(p_1)指向的位置就是倒数第k个节点。清楚了算法后我们就可以编程啦，但是本题还有坑点，如果链表长度小于k怎么办，如果有非法输入怎么办，例如输入(k leq 0),输入指针为NULL等等。考虑到这些特殊情况后代码如下：

#include <iostream>
using namespace std;

struct ListNode{
	int val;
	ListNode* next;
};

ListNode* FindKthToTail(ListNode* head, int k){
	if(head == nullptr || k <= 0) return nullptr;
	ListNode* p1 = head, *p2 = head;
	for(int i = 0; i < k; i++){
		if(p2 == nullptr) 	return nullptr;
		p2 = p2->next;
	}
	while(p2 != nullptr){
		p2 = p2->next;
		p1 = p1->next;
	}
	return p1;
}

int main(){
	// 测试，构建链表1->2->3->4
	ListNode *head = new ListNode;
	head->val = 1;
	ListNode *p = head;
	for(int i = 2; i < 5; i++){
		p->next = new ListNode;
		p = p->next;
		p->val = i;
	}
	p->next = nullptr;
	// 测试
	for(int i = 0; i < 6; i++){
		p = FindKthToTail(head, i);
		if(p == nullptr){
			printf("链表中倒数第%d个元素不存在
", i);
		}
		else{
			printf("链表中倒数第%d个元素为：%d
", i, p->val);
		}
	}
	// 测试空
	p = FindKthToTail(nullptr, 1);
	if(p == nullptr) puts("空输入测试通过");
	else puts("空输入测试error!");
	return 0;
}

面试题2：反转链表

定义一个函数，输入一个头节点，反转该链表

本题目要求反转链表，自然我们想到可以改变链表指针指向，此时只需要2个指针遍历一遍链表即可，需要注意特殊情况，当链表只有一个节点或者为空时直接返回即可。

#include <iostream>
using namespace std;

struct ListNode{
	int val;
	ListNode* next;
};

ListNode* reversedList(ListNode* head){
	if(head == nullptr || head->next == nullptr)
		return head;
	ListNode* pre = head;
	ListNode* last = head->next;
	ListNode* temp = nullptr;
	pre->next = nullptr;
	while(last != nullptr){
		temp = last->next; // 保存last下一个节点值
		last->next = pre;  // 当前节点与上一个节点链接
		pre = last;        // 更新pre
		last = temp;       // 更新last
	}
	return pre;
}

int main(){
	// 测试，构建链表1->2->3->4->5
	ListNode *head = new ListNode;
	head->val = 1;
	ListNode *p = head;
	for(int i = 2; i < 6; i++){
		p->next = new ListNode;
		p = p->next;
		p->val = i;
	}
	p->next = nullptr;
	head = reversedList(head);
	p = head;
	while(p){
		printf("%d ", p->val);
		p = p->next;
	}
	puts("");
	// 测试空节点
	p = reversedList(nullptr);
	if(p == nullptr) puts("pass");
	else puts("error");
	return 0;
}

面试题3：合并两个有序链表

题目：输入两个递增排序的链表，合并俩个链表并使得新链表的值也是递增的

合并算法很简单，直接按照顺序扫描即可。需要注意，合并的链表中间不要断开，特殊输入(空输入）要注意处理。

#include <iostream>
using namespace std;

struct ListNode{
	int val;
	ListNode* next;
};

ListNode* MergeList(ListNode* head1, ListNode* head2){
	if(head1 == nullptr) return head2;
	if(head2 == nullptr) return head1;
	ListNode* head = nullptr;
	if(head1->val <= head2->val){
		head = head1;
		head->next = MergeList(head1->next, head2);
	}
	else{
		head = head2;
		head->next = MergeList(head1, head2->next);
	}
	return head;
}

ListNode* CreateList(int a[], int n){
	if(n <= 0) return nullptr;
	ListNode* head = new ListNode;
	head->val = a[0];
	ListNode* p = head;
	for(int i = 1; i < n; i++){
		p->next = new ListNode;
		p = p->next;
		p->val = a[i];	
	}
	p->next = nullptr;
	return head;
}

void display(ListNode* head){
	if(head == nullptr) return;
	ListNode* p = head;
	while(p->next){
		printf("%d->", p->val);
		p = p->next;	
	}
	printf("%d
", p->val);
}

int main(){
	int a[5] = {-2, 0, 4, 8, 19};
	int b[4] = {0, 5, 8, 34};
	ListNode* head1 = CreateList(a, 5);
	ListNode* head2 = CreateList(b, 4);
	display(head2);
	display(head1);
	ListNode* head = MergeList(head1, head2);
	display(head);	 
	return 0;
}

单链表的实现

下面是我写的单链表类的实现，它包含两个头文件Node.h和LinkList.h分别是链表节点类与链表类的实现，还有一个main.cpp是测试使用的。

# ifndef _NODE_H_
#define _NODE_H_
// Node.h文件
// 节点类
template<class Type>
struct Node{
	Type data;
	Node<Type> *next;

	Node():next(nullptr) { };
	Node(Type &e, Node<Type>*link = nullptr );
};

template<class Type>
Node<Type>::Node(Type &e, Node<Type>*link){
	data = e;
	next = link;
}

#endif

#ifndef _LINKLIST_H_
#define _LINKLIST_H_

// LinkList.h头文件
// 链表数据结构

#include<iostream>
#include<Node.h>
using namespace std;

template<class Type>
class LinkList{
	private:
		Node<Type>*head; //  头
		int length;    // 长度

	public:
		LinkList();
		LinkList(Type a[],int n); // 数组初始化
		virtual ~LinkList();

		int getLength() const;    // 获取长度
		bool isEmpty() const;     // 判空
		void clear();             // 清空链表
		void traverse() const;    // 遍历输出
		int locateElem(Type e) const; // 返回位置
		bool getElem(int pos, Type&e) const; // 获取位置元素的值
		bool setElem(int pos, Type e); // 设置位置元素的值
		bool deleteElem(int pos, Type &e);   // 删除位置元素的值
		bool insertElem(int pos, Type e);  // 特定位置插入元素
		bool insertElem(Type e);          // 尾部插入元素
};

template<class Type>
LinkList<Type>::LinkList(){
	head = new Node<Type>;
	length = 0;
}

template<class Type>
LinkList<Type>::LinkList(Type a[], int n){
	head = new Node<Type>; 
	Node<Type>* p = head;
	for(int i = 0; i < n; i++){
		p->next = new Node<Type>(a[i]);
		p = p->next;
	}
	length = n;
}

template<class Type>
LinkList<Type>::~LinkList(){
	clear();
	delete head;
}

template<class Type>
int LinkList<Type>::getLength() const{
	return length;
}

template<class Type>
bool LinkList<Type>::isEmpty() const{
	return length == 0;
}

template<class Type>
void LinkList<Type>::clear(){
	Node<Type> *p = head->next;
	while(p != nullptr){
		head->next = p->next;
		delete p;
		p = head->next;
	}
	length = 0;
}

template<class Type>
void LinkList<Type>::traverse() const{
	Node<Type>*p = head->next;
	while(p != nullptr){
		cout << p->data << ' ';
		p = p->next;
	}
	cout << endl;
}

template<class Type>
int LinkList<Type>::locateElem(Type e) const{
	Node<Type> *p = head->next;
	int i = 1;
	while(p != nullptr && p->data != e){
		p = p->next;
		i++;
	}
	return i > length ? -1 : i;
}

template<class Type>
bool LinkList<Type>::getElem(int pos, Type&e) const{
	if(pos < 1 || pos > length) return false;
	Node<Type> * p = head->next;
	for(int i = 1; i <pos; i++){
		p = p->next;
	}
	e = p->data;
	return true;
}

template<class Type>
bool LinkList<Type>::setElem(int pos, Type e){
	if(pos < 1 || pos > length+1) return false;
	Node<Type> *p = head->next;
	for(int i = 1; i < pos; i++){
		p = p->next;
	}
	if(pos == length + 1)
		p = new Node<Type>(e);
	else p->data = e;
	return true;
}

template<class Type>
bool LinkList<Type>::deleteElem(int pos, Type &e){
	if(pos < 1 || pos > length) return false;
	Node<Type> *p = head, *q = nullptr;
	for(int i = 1; i < pos; i++){
		p = p->next;
	}
	q = p->next;
	p->next = q->next;
	e = q->data;
	delete q;
	length--;
	return true;
}

template<class Type>
bool LinkList<Type>::insertElem(int pos, Type e){
	Node<Type> *p = head->next, *pre = head;
	if(pos < 1 || pos > length+1) return false;
	for(int i = 1; i < pos; i++){
		pre = p;
		p = p->next;
	}
	if(p == nullptr){
		 p = new Node<Type>(e);
	}
	else {
		pre->next = new Node<Type>(e);
		pre = pre ->next;
		pre->next = p;
	}
	length++;
	return true;
}

template<class Type>
bool LinkList<Type>::insertElem(Type e){
	Node<Type>*p = head;
	while(p->next != nullptr){
		p = p->next;
	}
	p->next = new Node<Type>(e);
	length++;
	return true;
}

#endif

#include<LinkList.h>
#include<iostream>
using namespace std;
#define DEBUG

// main.cpp文件

int main(){
	#ifdef DEBUG
	LinkList<int> linklist;
	// 插入
	for(int i = 1; i <= 10; i++){
		linklist.insertElem(i);
	}
	// 遍历
	linklist.traverse();
	// 获得第i个元素
	for(int i = 1; i <= 11; i++){
		int x;
		if(linklist.getElem(i, x))
			printf("The %dth element is : %d
",i,x);
		else puts("nothing");
	}
	// 获得元素位置
	for(int i = 1; i <= 13; i+=3){
		printf("元素%d 的位置为 ： %d
",i, linklist.locateElem(i));
	}
	// 按位置插入
	for(int i = 0; i <= 12; i+=3){
		if(linklist.insertElem(i, i*i))
			printf("在第%d个位置成功插入: %d
", i, i*i);
		else printf("位置%d不合法
", i);
	}
	linklist.traverse();
	int x;
	for(int i = 0; i <= 12; i+=3){
		printf("当前元素为： ");
		linklist.traverse();
		if(linklist.deleteElem(i, x))
			printf("第%d个元素删除成功，删除值为：%d
", i, x);
		else printf("删除位置不合法
");
	}
	linklist.clear();
	if(linklist.isEmpty()) puts("当前元素已清空...");
	else puts("clear故障");
	double a[5] = {1.2, 45.7, 345.0, 78.7, -24.825 };
	LinkList<double> linklist_2(a, 5);
	linklist_2.traverse();

	#endif

	return 0;
}