链表相关操作

2019-04-04

数据结构与算法

链表相关操作

求单链表中结点的个数

将单链表反转

查找单链表中的倒数第K个结点（k > 0）

查找单链表的中间结点

从尾到头打印单链表

已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序

判断两个单链表是否相交

求两个单链表相交的第一个结点

判断一个单链表中是否有环

已知一个单链表中存在环，求进入环中的第一个结点

给出一单链表头指针pHead和一结点指针pToBeDeleted，O(1)时间复杂度删除结点pToBeDeleted

链表结构

 typedef  struct List {
	int val;
	List* next;
}*myList;
//创建链表
myList CreatList(unsigned int length)
{
	if (length == 0)
		return NULL;
	myList head, tail, temp;
	head = new List();
	head->next = NULL;
	tail = head;
	//在32位系统中size_t是4字节的，而在64位系统中，size_t是8字节的，这样利用该类型可以增强程序的可移植性。
	for (size_t i = 0; i < length; ++i){
		temp = new List();
		cin >> temp->val;
		temp->next = NULL;
		tail->next = temp;
		tail = temp;
	}
	temp = head;
	head = head->next;
	delete temp;
	return head;
}

1、求单链表中结点的个数

因为要求链表中结点的个数，因此只能遍历整个链表以确定结点个数。(；´д｀)ゞ

int Length(myList head)
{
	int length = 0;
	while (head) {
		length++;
		head = head->next;
	}
	return length;
}

2、将单链表反转

当链表中节点个数大于1时，保存链表的头结点为oldHead指针（因为反转后这就不是头指针了），
如果oldHead的后继结点不为空的话，使用指针temp储存这个结点，然后赋值oldHead的后继结点为其后继结点(即temp)的后继结点，然后将temp的后继结点设置为head结点，赋值head为temp；

void ReverseList(myList &head)
{
	if (head == NULL || head->next == NULL)
		return;
	myList temp, oldHead = head;
	while (oldHead->next) {
		temp = oldHead->next;
		oldHead->next = temp->next;
		temp->next = head;
		head = temp;
	}
}

3、查找单链表中的倒数第K个结点（k > 0）

使用两个指针left，right，先让right指向正数第k个结点，然后让left结点从头结点与right指针一同向后移动。当right指向最后一个结点时，left指向的就是倒数第k个结点。

myList FindCountBackwardsK(myList head, unsigned int k) 
{
	if (head == NULL)
		return NULL;
	myList  left = head, right = head;
	for (size_t i = 1; i < k; ++i){
		right = right->next;
		if (!right)
			return NULL;
	}
	while (right && right->next){
		right = right->next;
		left = left->next;
	}
	return left;
}

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

使用快慢指针，快指针每次向后移动两个结点的距离，慢指针每次向后移动一个指针距离，当快指针为空时，慢指针指向的结点便是中间结点。

myList FindMiddleNode(myList head)
{
	myList left = head, right = head;
	if (head == NULL)
		return NULL;
	while (right->next){
		right = right->next->next;
		if (right == NULL) 
			break;
		left = left->next;
	}
	return left;
}

5、从尾到头打印单链表

由从尾到头可以很容易想到能够使用递归或者栈来实现。使用递归时，在遇到链表尾结点时返回，然后打印结点的值。

//从尾到头打印单链表（递归）
void PrintListFromTailToHead(myList head)
{
	if (head == NULL)
		return;
	PrintListFromTailToHead(head->next);
	cout << head->val << endl;
}

//从尾到头打印单链表（通过栈）
void PrintListFromTailToHeadByStack(myList head)
{
	stack<myList> sta;
	while (head){
		sta.push(head);
		head = head->next;
	}
	while (!sta.empty()){
		cout << sta.top()->val << " ";
		sta.pop();
	}
	cout << endl;
}

6、已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序

可是使用归并排序的思想；选择值较小的头结点作为新的头结点，然后遍历两个链表，将值较小的结点合并到新链表中，遍历此链表的指针向后移位，另一个指针不做处理；当一个链表为空后，将不为空的链表合并到新链表中。

myList MergeOrderedLists(myList head1, myList head2)
{
	if (head1 == NULL)
		return head2;
	if (head2 == NULL)
		return head1;
	myList newHead =NULL;
	if (head1->val >= head2->val) {
		newHead = head2;
		head2 = head2->next;
	}
	else {
		newHead = head1;
		head1 = head1->next;
	}
	newHead->next = NULL;
	myList temp = newHead;
	while ( head1 && head2){
		if (head1->val < head2->val) {
			temp->next = head1;
			head1 = head1->next;
		}
		else {
			temp->next = head2;
			head2 = head2->next;
		}
		temp = temp->next;
		temp->next = NULL;
	}
	if (head1 == NULL) {
		temp->next = head2;
	}
	else {
		temp->next = head1;
	}
	return newHead;
}

7、判断两个单链表是否相交

从这点出发：若两个两链表相交，则这两个链表的尾结点必然相同。因此，我们可以分别遍历链表以得到他们的尾结点，然后判断两个尾结点的地址是否相同即可。

bool IsIntersect(myList head1, myList head2)
{
	if (head1 == NULL || head2 == NULL)
		return false;
	while (head1->next) {
		head1 = head1->next;
	}
	while (head2->next) {
		head2 = head2->next;
	}
	//若相交则两个链表的最后一个节点必然完全相等
	if (head1 == head2)
		return true;
	return false;
}

8、求两个单链表相交的第一个结点

两链表相交，求相交的第一个结点：先遍历两个链表，分别得到两个链表的长度。（储存一下尾结点，顺便判断一下两个链表是否相交）。求相交的第一个结点时，先让一个指针从长链表的头结点向前移动abs(len1-len2)个距离，然后让另一个指针从短链表头结点出发与这个指针一同向后移动，当两个指针首次指向同一个结点时，这个结点便是两个单链表相交的第一个结点。

myList FirstIntersectNode(myList head1, myList head2)
{
	if (head1 == NULL || head2 == NULL)
		return NULL;
	int len1 = 1, len2 = 1;
	myList temp1 = head1, temp2 = head2;
	while (temp1->next) {
		len1++;
		temp1 = temp1->next;
	}
	while (temp2->next) {
		len2++;
		temp2 = temp2->next;
	}
	//判断两链表是否相交
	if (temp1 != temp2)
		return NULL;
	//保证head1是两者中较长的链表
	if (len1 < len2) {
		temp1 = head1;
		head1 = head2;
		head2 = temp1;
	}
	for (int i = 0; i < abs(len1 - len2); ++i) {
		head1 = head1->next;
	}
	while (head2) {
		if (head1 == head2)
			return head1;
		head1 = head1->next;
		head2 = head2->next;
	}
	return NULL;
}

9、判断一个单链表中是否有环

可以使用快慢指针来判断单链表中是否存在环：使用两个指针fast、slow，slow每次向后移动一个结点的距离，fast每次向后移动两个结点的距离。若链表存在环的话，两个指针必然会相遇。

bool IsCircularList(myList head)
{
	if (head == NULL && head->next == NULL)
		return false;
	myList temp1 = head, temp2 = head;
	//temp1和temp2都不为空
	while (temp1 && temp2 && temp2->next)
	{
		temp1 = temp1->next;
		temp2 = temp2->next->next;
		if (temp1 == temp2)
			return true;
	}
	return false;
}

10、已知一个单链表中存在环，求进入环中的第一个结点

设链表头距离环入口的长度为L，快慢指针相遇的位置为cross，该位置距离环入口的长度为S。考虑快慢指针移动的距离，慢指针走了L+S，快指针走了L+S+nR(n表示两只镇相遇前快指针走的圈数)。由于快指针的速度是慢指针的两倍，相同时间下快指针走过的路程就是慢指针的两倍，所以有2(L+S)=L+S+nR，化简得L+S=nR
当n=1时，即快指针在相遇之前多走了一圈，即L+S=R，也就是L=R−S，因此可以使用两个指针，一个指针从链表头部移动，一个从快慢指针第一次相遇处的后个指针开始移动，每次移动一个节点的距离，则两指针相等时所指向的结点就是进入环的第一个结点。

myList CircularListEntrance(myList head)
{
	if (head == NULL)
		return NULL;
	myList fast = head, slow = head;
	while (slow && fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		//第一次相交
		if (slow == fast) {
			fast = head;
			while (slow != fast) {
				//这里让指向第一次相遇处的指针先走
				slow = slow->next;
				fast = fast->next;
			}
			return slow;
		}
	}
	return NULL;
}

11、给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除结点pToBeDeleted

因为每个结点的储存结构都是相同的，因此，当pToBeDeleted不是尾结点时，可以将pToBeDeleted下个节点储存的数据复制到pToBeDeleted结点中，然后进行删除pToBeDeleted-next的操作即可。当pToBeDeleted为尾结点时，就需要遍历整个链表找到pToBeDeleted结点的前驱结点了。不过时间复杂度总体上讲为O(1);

void DeleteNode(myList head, myList pToBeDeleted)
{
	if (head == NULL)
		return;
	if (pToBeDeleted->next != NULL) {
		myList temp = pToBeDeleted->next;
		pToBeDeleted->val = temp->val;
		pToBeDeleted->next = temp->next;
		delete temp;
		temp = NULL;
	}
	else {
		if (head == pToBeDeleted) {
			delete pToBeDeleted;
			head = NULL;
			pToBeDeleted = NULL;
		}
		while (head->next != pToBeDeleted) {
			head = head->next;
		}
		head->next = NULL;
		delete pToBeDeleted;
		pToBeDeleted = NULL;
	}
}

链表相关操作

链表相关操作

1、求单链表中结点的个数

2、将单链表反转

3、查找单链表中的倒数第K个结点（k > 0）

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

5、从尾到头打印单链表

6、已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序

7、判断两个单链表是否相交

8、求两个单链表相交的第一个结点

9、判断一个单链表中是否有环

10、已知一个单链表中存在环，求进入环中的第一个结点

11、给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除结点pToBeDeleted

上一页

常用排序算法

算法

下一页

递归创建二叉树时为什么要传指针的引用？

C++ 二叉树  指针

评论