数据结构篇——线性表之链表

1、单链表

（1）定义

它是线性表的链式存储方式之一，通过一组任意的储存单元来存储线性表中的数据元素。为了维护数据元素之间的线性关系，对于每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

（2）特点

• 不需要连续的存储空间，但需要增加指针域这一储存开销；
• 无法进行随机存取；
• 已知插入和删除节点的前驱结点时，可在O(1)时间内完成插入和删除。

注：为了操作的方便，通常在单链表的第一个结点之前附加一个结点，这个节点通常不储存任何信息。

（3）基本操作（注：以下操作的单链表都带了一个头结点）

① 建表：创建一个单链表来表示线性表。（这里采用尾插法）

// 将data的类型定义为整型
typedef int ElemType;
// 单链表的结点类型
// LNode代表结点，LinkList代表链表
typedef struct LNode {
	ElemType data;
	LNode *next;
}LNode, *LinkList;	

// 创建链表
LinkList createLinkList(ElemType *a = NULL, int len = 0) {
	// 创建头结点
	LinkList L = new LNode;
	// 创建所有数据结点
	LNode *pre = L, *cur;
	for (int i = 0; i < len; i++) {
		// 生成一个新结点
		cur = new LNode;
		cur->data = a[i];
		// 衔接到链表
		pre->next = cur;
		pre = pre->next;
	}
	// 链表尾部
	pre->next = NULL;
	return L;
}

②判空：判断一个单链表是否是空表。

// 判断一个单链表是否是空表
bool isEmpty(LinkList L) {
	return (L->next == NULL);
}

③按序号查找：按序号进行查找，返回结点指针。

// 按序号查找结点
// T = O(n), S = O(1)
LNode* findByIndex(LinkList L, int i) {
	// i太小
	if (i <= 0) {
		return NULL;
	}

	LNode *p = L;
	int j = 1;
	// 遍历链表
	for (; p != NULL && j <= i; j++, p = p->next) {
		// 空循环体
	}
	return p;
}

④ 按值查找：返回单链表中第一个数据域为指定数值的结点指针。

// 按值查找结点
// T = O(n), S = O(1)
LNode* findByValue(LinkList L, ElemType value) {
	for (LNode *p = L->next; p != NULL; p = p->next) {
		if (p->data == value) {
			return p;
		}
	}
	return NULL;
}

⑤插入：先找到插入结点的前驱结点指针，再进行插入。

// 在指定位置插入结点，返回插入结果
// T = O(n), S = O(1)
bool insert(LinkList& L, int i, ElemType e) {
	// 寻找前驱结点L[i-1]
	LNode *pre = (i == 1 ? L : findByIndex(L, i - 1));
	// 判断是否可以插入
	if (pre == NULL) {
		return false;
	}

	// 正常插入
	LNode *cur = new LNode;
	cur->data = e;
	cur->next = pre->next;
	pre->next = cur;
	return true;
}

⑥删除：删除指定位置的节点，返回删除是否成功的信息，并将被删除的节点的数据域存放在参数e中。

// 删除指定位置的结点，返回删除结果
// T = O(n), S = O(1)
bool del(LinkList& L, int i, ElemType& e) {
	// 寻找前驱结点L[i-1]
	LNode *pre = (i == 1 ? L : findByIndex(L, i - 1));
	// 判断是否可以删除
	if (pre == NULL || pre->next == NULL) {
		return false;
	}

	// 正常删除
	LNode *cur = pre->next;
	pre->next = cur->next;
	e = cur->data;
	delete cur;
	return true;
}

⑦求表长：遍历单链表，求出单链表的长度。

// 求表长
// T = O(n), S = O(1)
int getLen(LinkList L) {
	int len = 0;
	for (LNode *p = L->next; p != NULL; p = p->next) {
		len++;
	}
	return len;
}

⑧翻转链表：从第2个结点开始，依次获取结点p，并将p插入到单链表，让p成为第一个结点；当单链表遍历结束后，单链表便成功被翻转。

// 翻转链表
// T = O(n), S = O(1)
void reverse(LinkList& L) {
	// 空表不必修改
	if (L->next == NULL) {
		return;
	}

	// 翻转后的尾结点是第一个数据结点
	LNode *tailNode = L->next;
	while (tailNode->next != NULL) {
		// 依次获取尾结点后面的结点
		LNode *firstNode = tailNode->next;
		tailNode->next = firstNode->next;
		// 插入到头部
		firstNode->next = L->next;
		L->next = firstNode;
	}
}

⑨有序链表合并：将两个升序的单链表合并成一个有序的单链表。

// 有序链表合并
// T = O(m + n), S = O(1)
LinkList merge(LinkList L1, LinkList L2) {
	// 合并到L3
	LinkList L3 = new LNode;
	
	// 开始合并
	LNode *p1 = L1->next, *p2 = L2->next, *p3Pre = L3;
	// 两个链表均未结束
	while (p1 != NULL && p2 != NULL) {
		p3Pre->next = new LNode;
		p3Pre = p3Pre->next;
		if (p1->data < p2->data) {
			p3Pre->data = p1->data;
			p1 = p1->next;
		}
		else {
			p3Pre->data = p2->data;
			p2 = p2->next;
		}
	}
	// 拷贝剩下部分
	while (p1 != NULL) {
		p3Pre->next = new LNode;
		p3Pre = p3Pre->next;
		p3Pre->data = p1->data;
		p1 = p1->next;
	}
	while (p2 != NULL) {
		p3Pre->next = new LNode;
		p3Pre = p3Pre->next;
		p3Pre->data = p2->data;
		p2 = p2->next;
	}
	// 补上结束标志
	p3Pre->next = NULL;

	return L3;
}

（3）相关习题

①对给定的单链表（带头结点）进行插入排序。

算法思想：

I. 在第一个结点和第二个结点之间进行断链得到sL和uL，将sL（只有一个结点）视为有序的；

II. 获取uL的头结点，在sL中找到合适的位置，将其插入；

III. 重复步骤II，知道uL为空表。

// 单链表插入排序
// T = O(n²), S = O(1)
void insertSort(LinkList& L) {
	// 判空
	if (L->next == NULL) {
		return;
	}

	// 断链，将链断为有序链L和无序链uL两部分
	LNode *uL = L->next->next;
	L->next->next = NULL;
	
	// 遍历无序链
	while (uL != NULL) {
		// 移出无序链的头结点iNode
		LNode *iNode = uL;
		uL = uL->next;
		// 寻找插入点的前驱
		LNode *iPreNode = L, *iNextNode = L->next;
		while (iNextNode != NULL && iNode->data >= iNextNode->data) {
			iPreNode = iPreNode->next;
			iNextNode = iNextNode->next;
		}
		// iNode插入到有序链
		iPreNode->next = iNode;
		iNode->next = iNextNode;
	}
}

②对给定的单链表（带头结点）进行快速排序。

I. 实现辅助函数moveNode(&pPre, &qPre)。

给定的参数pPre和qPre分别是p结点和q节点的前驱结点指针引用（第一个结点的前驱结点认为是头结点），要实现将q结点移动到p结点前面，并保证pPre一直是p的前驱结点。

只需对给定的前驱结点指针做一些修改便能完成这一操作。值得注意的是，刚将q结点移动到p结点的前面时，pPre已经不再是p结点的前驱结点，需要对它进行刷新。

// 将q节点移动到p节点之前
// T = O(1), S = O(1)
void moveNode(LNode* &pPre, LNode* &qPre) {
	// 获取移动的结点
	LNode *q = qPre->next;
	// 移除q结点，更新qPre
	qPre->next = q->next;
	// 插入到pPre和p之间
	q->next = pPre->next;
	pPre->next = q;
	// 刷新pPre
	pPre = pPre->next;
}

II. 实现排序函数quickSort(&beginPre, end = NULL)。

其中beginPre为需排序单链表的第一个结点的前驱结点指针，end是需排序单链表的最后一个结点的假想后继（默认为NULL）。

算法思想：

a. 用指针p指向第一个结点（本趟排序的枢纽），q指向第二个结点，同时记录p的前驱结点pPre和q的前驱结点qPre;

b. 若q->data >= p->data，qPre和q均向前移动一个结点；否则，利用moveNode函数，将q结点移动到p结点之前，同时需要刷新q结点，令q = qPre->next。

c. 反复执行b步骤，直到q == end。此时p的左边均小于p，p的右边均不小于p，再借助递归进行解决p的左边和右边。

以下是一趟排序的过程：

// 单链表快速排序，排序区间为[beginPre->next, end)
// T = O(nlgn), S = O(lgn)
void quickSort(LNode *&beginPre, LNode *end = NULL) {
	LNode *begin = beginPre->next;
	// 只有一个元素直接结束
	if (begin == end || begin->next == end) {
		return;
	}

	// p是枢纽指针，q是遍历指针
	LNode *pPre = beginPre, *p = begin;
	LNode *qPre = begin, *q = begin->next;

	// 分隔
	while (q != end) {
		// 需要交换，qPre不用动，q被移除后要刷新
		if (q->data < p->data) {
			moveNode(pPre, qPre);
			// 注意刷新p和q，否则p和q还是指向交换前的元素
			p = pPre->next;
			q = qPre->next;
		}
		// 无需交换，q直接前行
		else {
			qPre = qPre->next;
			q = q->next;
		}
	}

	// 递归处理
	quickSort(beginPre, p);
	quickSort(p, end);
}

③利用递归，删除不带头结点的单链表L的所有值为value的节点。

思路：这里必须借助C++的引用，因为对于结点p，很难获取它的前驱结点。但如果使用引用&p，那这个变量p刚好就是p的前驱结点的指针域的别名，修改p就相当于修改p的前驱结点的指针域，这样便可以达到删除的目的。

// 利用递归算法，删除不带头结点的单链表L的所有值为value的节点
// T = O(n), S = O(n)
void delByValue(LinkList& L, ElemType value) {
	// 递归停止
	if (L == NULL) {
		return;
	}
	// 不相等，继续前行
	if (L->data != value) {
		delByValue(L->next, value);
	}
	// 相等，删除后前行
	else {
		LNode *p = L;
		L = L->next;	// L是引用，即L是当前结点的前驱结点的指针域
		delete p;
		delByValue(L, value);
	}
}

④只遍历一次单链表，返回倒数第k个结点。

算法思想：使用快慢指针，q是慢指针，p是快指针。一开始，p向前运动而q保持静止。当p走过k个结点时，q开始运动；那么，当q走到链尾时，p就是倒数第k个结点。

// 只遍历一次单链表，返回倒数第k个结点
// T = O(n), S = O(1)
LNode* findByRecIndex(LinkList L, int k) {
	// 不合法的k
	if (k <= 0) {
		return NULL;
	}

	// p是快指针，q是慢指针
	LNode *p = L->next, *q = L->next;
	int count = 0;
	for (; p != NULL; p = p->next) {
		// 前k步q不走
		if (count < k) {
			count++;
		}
		else {
			q = q->next;
		}
	}

	return (count >= k ? q : NULL);
}

⑤给定两个单链表（带头结点），找出它们的第一个公共结点。

I. 如果给定的链表是等长的，即L1.len == L2.len。那么问题将变简单，只需让p指向L1，q指向L2，然后p和q同时运动，当出现p == q时，说明第一个公共结点被找到。

II. 如果两个链表长度不相等，那么可以先算出它们的长度之差d，然后先让长链表走d个结点，此时问题就变成了等长时的情况了。

2、循环单链表：循环单链表基本与单链表相同，唯一不同的是，它最后一个结点的指针域不是NULL，而是指向了头结点。故其判空的条件为L->next == L。

3、循环双链表：它的结点有两个指针域——prior和next。其中prior指向当前结点的前驱结点，next指向当前结点的后继节点。其判空的条件为L->prior == L && L->next == NULL。

4、静态链表：静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，但是它的指针并不是真正的指针，只是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。此外，next=-1是静态链表的结束标志。

5、顺序表与链表的比较