链表练习题

前言

一些链表的面试题，再此记录以便日后复习

从尾到头打印链表元素

题目要求：逆序打印链表
思路：定义两个指针，一个指针用来进行遍历，一个指针指向链表的末端，从末端开始打印，每打印完一个元素后末端指针向前移一位，直到和list指向同一个节点

//非递归写法
void TailToHeadPrint(Node *list)
{
	Node *cur = list;
	Node *last = NULL;

	while (last != list)
	{
		cur = list;
		while (cur->next != last)
		{
			cur = cur->next;
		}
		printf("%d  ", cur->data);
		last = cur;
	}
	printf("\n");
}

//递归写法 
//1.递归法从尾到头打印链表（在递归的最后一层打印头节点）
void TailToHeadPrint_R(Node* plist)
{
	if (NULL == plist->next)
	{
		printf("%d--->", plist->data);
		return;
	}
	else
	{
		TailToHeadPrint_R(plist->next);
		printf("%d--->", plist->data);
	}
}

//2.递归法从尾到头打印链表（统一在函数调用结束时打印各元素）
void TailToHeadPrint_R2(Node* plist)
{
	if (NULL == plist)
	{
		return;
	}
	else
	{
		TailToHeadPrint_R(plist->next);
		printf("%d--->", plist->data);
	}
}

逆置/反转链表

题目要求：将链表内的所有节点逆置
思路：用头删的方法将节点依次拿出，在使用头插的方法将节点插入到新的链表中去

Node *Reverse(Node *first)
{
	Node *cur = first;
	Node *node = NULL;     //记录每一个节点
	Node *result = NULL;  //新链表的指针
	while (cur != NULL)
	{
		//将节点从前往后依次摘下，用node记录
		node = cur;
		cur = cur->next;
		//头插入目标链表
		node->next = result;
		result = node;
	}
	PrintLinkList(result);
}

在无头单链表的一个节点前插入一个节点（不能遍历链表）

题目要求：在指定节点前插入一个节点
思路：依然采用替换的思想，在目标节点后方插入一个节点，然后交换两个节点的数据，则达到题目要求

void zhidingweizhiqiancharu(Node *node,DataType data)
{
	Node *newNode = (Node*)malloc(sizeof(Node));
	
	newNode->data = node->data;
	newNode->next = node->next;
	node->next = newNode;
	node->data = data;  
}

删除一个无头单链表的非尾结点(不能遍历链表)

题目要求：删除链表中指定位置的一个非尾节点,此处只是将节点当作盛放数据的容器，且数据和容器没有捆绑在一起的情况
思路：采用替换法删除，所有此类删除只适用于数据和节点地址无需绑定的情况。

//删除一个无头单链表的非尾结点（不能遍历链表） 此处只是将节点当作盛放数据的容器，且数据和容器没有捆绑在一起的情况
void RemoveNoHeadNoTail(Node *node)   //此处传上来的实参为所要删除节点的地址
{
	Node *Next = node->next;
	node->data = Next->data;
	node->next = Next->next;
	free(Next);
}

约瑟夫环问题

题目要求：将一个链表连接成环，删除环中节点直到只剩下一个节点为止
思路：从某一个节点(这里第一次从初节点)开始，每次都删除这个节点后第三个节点，直到环中只剩下一个节点

void Joceph(Node* first, int k)
{
	//构成环
	Node *cur = first;
	while (cur->next != NULL)
	{
		cur = cur->next;
	}
	cur->next = cur;
	//删除节点，每次删除指定位置后第三个节点
	cur = first;     //cur为要删除的节点
	//要删除一个节点及是让他后面的节点指向他前面的节点，然后释放该节点，如下图
	Node *prev = NULL;   //用prev记录cur后面的一个节点
	while (cur->next != cur)
	{
		for (int i = 0; i < k - 1; i++)
		{
			prev = cur;
			cur = cur->next;
		}

		prev->next = cur->next;
		free(cur);

		cur = prev->next;
	}
	printf("%d\n", cur->data);
}

删除节点示意图:

合并两个有序链表，合并后依然有序

题目要求：将两条有序链表合为一条有序链表
思路：从两条链表的首节点开始依次进行比较，将较小的节点保存在node中，采用尾插的方式插入到结果链表result中去

Node* Merge(Node *list1, Node* list2)
{
	Node *cur1 = list1;
	Node *cur2 = list2;
	Node *node = NULL;
	Node *result = NULL;
	Node *tail = NULL;
	while (cur1 != NULL && cur2 != NULL)
	{
		if (cur1->data <= cur2->data)  //找到两个链表中较小节点
		{
			node = cur1;   //node是要插入结果链表中的节点
			cur1 = cur1->next;

			//在结果链表中尾插
			if (tail == NULL)
			{
				result = node;
			}
			else
			{
				tail->next = node;
			}
			node->next = NULL;
			//node 成为新的最后一个节点
			tail = node;
		}
		else{
			node = cur2;
			cur2 = cur2->next;

			if (tail == NULL)
			{
				result = node;
			}
			else{
				tail->next = node;
			}
			node->next = NULL;

			tail = node;
		}	
	}

	if (cur1 != NULL)
	{
		tail->next = cur1;
	}

	if (cur2 != NULL)
	{
		tail->next = cur2;
	}

	PrintLinkList(result);
}

求两个已排序单链表中相同的数据

题目要求：给定两个已排好序的链表，打印出两天链表中相同的节点
思路：在一个循环内同时推进两个链表。从第一个节点开始比较两个节点的大小。直至相等打印然后两个指针同时往后继续比较

void FindSomeNode(Node *list1, Node *list2)
{
	Node *cur1 = list1;
	Node *cur2 = list2;

	while (cur1 != NULL && cur2 != NULL)
	{
		while (cur1!=NULL && cur2!=NULL && cur1->data > cur2->data)
		{
			cur2 = cur2->next;
		}

		if (cur2 == NULL)
		{
			break;
		}

		while (cur1!=NULL && cur2!=NULL && cur1->data < cur2->data)
		{
			cur1 = cur1->next;
		}

		if (cur1 == NULL)
			break;

		while (cur1!=NULL && cur2!=NULL && cur1->data == cur2->data)
		{
			printf("%d ",cur1->data);
			cur1 = cur1->next;
			cur2 = cur2->next;
		}
	}
}

查找单链表的中间节点，要求只能遍历一次

题目要求：在一条已知链表中查找他的中间节点，并打印出他的数据域，只能遍历一次
思路：采用快慢指针的方法，定义两个指针，其中快指针走两步让慢指针走一步，这样快指针的速度总是慢指针的两倍，当快指针停下来的时候，慢指针刚好走了快指针的一半路程。所以当快指针遍历完了整个链表，此时慢指针的位置便是中间节点的位置。当链表节点数为偶数时，中间节点为中间两个节点中第一个节点

Node * MidFFind(Node* first)
{
	Node *fast = first;
	Node *slow = first;

	//要注意避免对空指针的解引用情况，所以快每走一步都应该判断一下指针不为空
	while (1)
	{
		fast = fast->next;
		if (fast == NULL)
		{
			break;
		}
		fast = fast->next;
		if (fast == NULL)
		{
			break;
		}
		slow = slow->next;
	}
	printf("%d ", slow->data);
}

查找单链表的倒数第k个节点，要求只能遍历一次

题目要求：再已知链表中查找倒数第k个节点，要求只能遍历一次链表
思路：设置两个指针，让第一个指针先走到k-1处，然后两个指针一起走，当第一个指针走到链表最后的时候停下来，此时第二个指针指向的便是所要查找到的节点

Node * FindLastNode(Node *list, int k)
{
	Node *first = list;
	Node *second = list;
	for (int i = 0; i < k - 1; i++)
	{
		first = first->next;
	}

	while (first->next != = NULL)
	{
		first = first->next;
		second = second->next;
	}
	return second;
}

复杂链表的复制

题目要求：一个链表的每个节点，有一个next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL
现在要求实现复制这个链表，返回复制后的新链表

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int DataType;
typedef struct Node
{
	DataType data;
	struct Node *next;
	struct Node *random;
}Node;

Node* creatNode(DataType data)
{
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->next = newNode->random = NULL;
	return newNode;
}

Node* LinkInit()
{
	Node *n1 = creatNode(1);
	Node *n2 = creatNode(2);
	Node *n3 = creatNode(3);
	Node *n4 = creatNode(4);
	n1->next = n2; n2->next = n3; n3->next = n4;
	n1->random = n3; n2->random = n1; n3->random = n3;
	return n1;
}

Node* copy(Node *list)
{
	//复制链表每个节点，让新的节点跟在老的节点后面
	Node *cur = list;   //cur 只遍历老的节点
	Node *newNode;
	while (cur != NULL)
	{
		newNode = creatNode(cur->data);
		newNode->next = cur->next;
		cur->next = newNode;
		cur = newNode->next;
	}
	//复制random字段
	cur = list;
	while (cur != NULL)
	{
		newNode = cur->next;
		if (cur->random != NULL)
		{
			newNode->random = cur->random->next;
		}
		cur = cur->next->next;
	}
	//将连起来的链表拆分成两个链表
	cur = list;
	Node *Next, *newNext;
	Node *result = list->next;
	while (cur != NULL)
	{
		newNode = cur->next;
		Next = newNode->next;
		if (Next == NULL)
		{
			newNext = NULL;
		}
		else
		{
			newNext = Next->next;
		}

		cur->next = Next;
		newNode->next = newNext;

		cur = Next;
	}
	return result;
}

void PrintLinkList(Node *list)
{
	Node *cur = list;
	while (cur != NULL)
	{
		printf("%d  ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

int main()
{
	Node *list = LinkInit();
	Node *ret = copy(list);
	PrintLinkList(ret);
	system("pause");
	return 0;
}