链表的常见实现

待我称王封你为后i 2022-08-14 02:54 142阅读 0赞

链表结点声明如下：

struct LinkList {
    	int value;
    	LinkList *next;
    };

**以下是不带头结点的单链表的操作。**

# 1. 根据输入建立单链表 #

将输入的节点插入到链表头部。

//根据输入建立单链表：链表头部插入
    LinkList *BuildList() {
    	LinkList *head = NULL;
    	int data;
    	int i = 0;
    	while (scanf("%d", &data) != EOF) {
    		//scanf("%d", &data);++i;
    		LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));
    		if (NULL == new_node) {
    			fprintf(stderr, "malloc failed");
    			return head;
    		}
    		new_node->value = data;
    		if (head == NULL) {
    			new_node->next = NULL;
    			head = new_node;
    		}
    		else {
    			new_node->next = head;
    			head = new_node;
    		}
    	}
    	return head;
    }

# 2. 链表插入操作 #

链表插入时注意当链表为空的情况。

## （1）在链表头插入 ##

//在链表头部插入节点
    LinkList *InsertToHead(int value, LinkList *head) {
    	LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));
    	if (new_node == NULL) {
    		fprintf(stderr, "malloc failed");
    		return head;
    	}
    	new_node->value = value;
    	new_node->next = NULL;
    	if (head == NULL) {
    		head = new_node;
    	}
    	else {
    		new_node->next = head;
    		head = new_node;
    	}
    	return head;
    }

## （2）在链表尾部插入 ##

//链表尾部插入节点
    LinkList *InsertToTail(int value, LinkList *head) {
    	LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));
    	if (new_node == NULL) {
    		fprintf(stderr, "malloc failed");
    		return head;
    	}
    	new_node->value = value;
    	new_node->next = NULL;
    
    	if (head == NULL)
    		head = new_node;
    	else {
    		LinkList *pnode = head;
    		while (pnode->next != NULL)
    			pnode = pnode->next;
    		pnode->next = new_node;
    	}
    	return head;
    }

# 3. 链表的删除操作 #

注意当链表仅有一个节点时的删除。

//删除某节点
    LinkList *DeletebyValue(int value, LinkList* head) {
    	if (head == NULL)
    		return head;
    	LinkList *pToDelete = NULL;
    	if (head->value == value) {
    		pToDelete = head;
    		head = head->next;
    	}
    	else {
    		LinkList *p = head;
    		while (p->next != NULL && p->next->value != value)
    			p = p->next;
    		if (p->next != NULL) {
    			pToDelete = p->next;
    			p->next = pToDelete->next;
    		}
    	}
    	if (pToDelete != NULL) {
    		free(pToDelete);
    		pToDelete = NULL;
    	}
    	return head;
    }

# **4. 求单链表中结点的个数** #

注意检查链表是否为空。时间复杂度为O（n）。该操作不用特意检查链表是否为空，如下代码，链表为空会返回0**。**

unsigned int Length(LinkList *head) {
    	unsigned int length = 0;
    	LinkList *p = head;
    	while (p) {
    		++length;
    		p = p->next;
    	}
    	return length;
    }

# **5. 打印链表元素** #

## （1）正向打印链表 ##

//打印单链表
    void PrintList(LinkList *head) {
    	LinkList *p = head;
    	while (p) {
    		printf("%d ", p->value);
    		p = p->next;
    	}
    	printf("\n");
    }

## （2）逆序打印链表 ##

//逆序打印单链表：非递归
    void RPrintList(LinkList* head) {
    	if (NULL == head)
    		return;
    	stack<int> list_stack;
    	while (head) {
    		list_stack.push(head->value);
    		head = head->next;
    	}
    	while (!list_stack.empty()) {
    		printf("%d ", list_stack.top());
    		list_stack.pop();
    	}
    	printf("\n");
    }
    
    //逆序打印单链表：递归
    void RPrintListRecursively(LinkList* head) {
    	if (NULL == head)
    		return;
    	else {
    		RPrintListRecursively(head->next);
    		printf("%d ", head->value);
    	}
    }

# 6.为单链表的元素排序 #

由于单链表只有通过其next指针才能获取下一个元素，因此，对单链表的排序只能采用向后遍历的排序方法，例如[冒泡排序的改进][Link 1]。而不能使用如插入排序、快速排序等需要向前查找的算法。如下算法是用冒泡排序进行的。一趟排序将未排序子序列中最大的元素放到链表已经排序子序列的头部（此最大元素是已排序子序列中的最小值）。

//冒泡排序单链表
    LinkList* Sort(LinkList *head) {
    	if (NULL == head)
    		return head;
    	int length = Length(head);
    	int unorder_size = length;
    	int flag = 1;
    	while (flag) {
    		flag = 0;
    		LinkList *p = head;
    		for (int i = 0; p->next && i < unorder_size; ++i) {
    			if (p->value > p->next->value) {
    				int temp = p->value;
    				p->value = p->next->value;
    				p->next->value = temp;
    				flag = 1;
    			}
    			p = p->next;
    		} 
    		--unorder_size;
    	}
    	return head;
    }

# 7. 单链表的翻转 #

从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O（n）

//翻转单链表
    LinkList* ReverseList(LinkList *head) {
    	//其实这里if判断当链表节点个数小于两个的情况
    	//不是必须的，因为之后的程序包含这里的判断
    	if (NULL == head || NULL == head->next){
    		return head;
    	}
    	LinkList *reverse_head = NULL;  //翻转后链表的头指针
    	LinkList *pcurrent = head;      //pcurrent遍历链表
    	while (pcurrent) {
    		LinkList* temp = pcurrent;
    		pcurrent = pcurrent->next;
    		temp->next = reverse_head;
    		reverse_head = temp;
    	}
    	return reverse_head;
    }

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

最容易想到的方法：先统计单链表中结点的个数，然后再找到第（n-k）个结点。注意链表为空，k为0，k为1，k大于链表中节点个数时的情况。时间复杂度为O（n）。

**另一种思路**：仅需遍历一次单链表。

主要思路就是使用两个指针，先让前面的指针走到正向第k个结点，这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点。

注意链表节点个数小于k的情况。

//找出链表倒数第k个节点（k > 0)
    LinkList * GetRKthNode(LinkList *head, int k) {
    	if (k < 1 || NULL == head)
    		return NULL;
    	LinkList *first = head;
    	LinkList *second = head;
    
    	//如果节点个数小于k返回NULL
    	for (int i = 1; i < k; ++i) {
    		if (second->next)
    			second = second->next;
    		else
    			return NULL;
    	}
    
    	//两个指针同时移动，直到快的second指针走到最后一个节点，
    	//此时慢的first指针指向的就是倒数第k个节点
    	while (second->next != NULL) { 
    		first = first->next;
    		second = second->next;
    	}
    	return first;
    }

# **9. 查找单链表的中间结点** #

此题可用于上一题类似的思想。也是设置两个指针，只不过这里是，两个指针同时向前走，前面的指针每次走两步，后面的指针每次走一步，前面的指针走到最后一个结点时，后面的指针所指结点就是中间结点：第n / 2 + 1个结点。

当链表元素个数为偶数时，代码返回的是n/2 + 1个结点，这个应该讨论：也许需要返回的是中间两个节点或者他们的平均值。

注意链表为空，链表结点个数为1和2的情况。时间复杂度O（n）：

//返回单链表的中间节点，当链表节点个数为偶数时
    //该函数返回链表第n/2 + 1个节点
    LinkList *GetMiddleNode (LinkList* head) {
    	//链表为空或者仅有一个节点
    	if (NULL == head || NULL == head->next)
    		return head;
    
    	LinkList *first = head;
    	LinkList *second = head;
    	while (second->next) {
    		first = first->next;
    		second = second->next;
    		if (second->next) {  //当节点个数为偶数时情况比较特殊
    			second = second->next;
    		}
    	}
    	return first;
    }

# **10. 合并两个有序的单链表** #

使得合并后链表仍有序，如下代码保留值相同的元素。

这个类似归并排序。尤其注意两个链表都为空的情况，和其中一个为空时的情况。只需要O（1）的空间。时间复杂度为O（max(len1, len2)）。

//合并两个有序的单链表：非递归
    //链表原来相等的元素都保留
    LinkList* MergeList(LinkList* heada, LinkList *headb) {
    	if (NULL == heada)
    		return headb;
    	if (NULL == headb)
    		return heada;
    
    	LinkList *head_merge = NULL;
    
    	//比较第一个节点大小，取小者作为合并后第一个节点
    	if (heada->value <= headb->value) {
    		head_merge = heada;
    		//注意下面两条语句顺序不能换，否则heada将指向空
    		heada = heada->next;
    	}
    	else {
    		head_merge = headb;
    		//注意下面两条语句顺序不能换，否则headb将指向空
    		headb = headb->next;
    		//head_merge->next = NULL;
    	}
    	head_merge->next = NULL;
    
    	LinkList *pmerge = head_merge;
    	while(heada != NULL && headb != NULL) {
    		if (heada->value <= headb->value) {
    			pmerge->next = heada;
    			heada = heada->next;
    			pmerge = pmerge->next;
    			
    		}
    		else {
    			pmerge->next = headb;
    			headb = headb->next;
    			pmerge = pmerge->next;
    		}
    		pmerge->next = NULL;
    	}
    	if (heada)
    		pmerge->next = heada;
    	else if (headb)
    		pmerge->next = headb;
    
    	return head_merge;
    }
    
    //合并两个有序的单链表：递归
    //链表原来相等的元素都保留
    LinkList* MergeListRecursively(LinkList *heada, LinkList *headb) {
    	if (NULL == heada)
    		return headb;
    	if (NULL == headb)
    		return heada;
    	
    	LinkList *head_merge = NULL;
    	if (heada->value <= headb->value) {
    		head_merge = heada;
    		head_merge->next = MergeListRecursively(heada->next, headb);
    	}
    	else {
    		head_merge = headb;
    		head_merge->next = MergeListRecursively(heada, headb->next);
    	}
    	return head_merge;
    }

# **11. 判断一个单链表中是否有环** #

这里也是用到两个指针。如果一个链表中有环，也就是说用一个指针去遍历，是永远走不到头的。因此，我们可以用两个指针去遍历，一个指针一次走两步，一个指针一次走一步，如果有环，两个指针肯定会在环中相遇。时间复杂度为O（n）。

//判断链表中是否有环
    bool HasCircle(LinkList *head) {
    	if (NULL == head)
    		return false;
    	LinkList *first = head;
    	LinkList *second = head;
    	while (first && second->next) {
    		second = second->next->next;
    		first = first->next;
    		if (first == second)
    			return true;
    	}
    	return false;
    }

# **12. 判断两个单链表是否相交** #

**如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的**。也就是说，**如果两个链表相交，那么最后一个节点肯定是共有的**。先遍历第一个链表，记住最后一个节点，然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则不相交。时间复杂度为O(len1+len2)，因为只需要一个额外指针保存最后一个节点地址，空间复杂度为O(1)。

//判断两个链表是否相交
    bool IsCross(LinkList* heada, LinkList *headb) {
    	if (NULL == heada || NULL == headb)
    		return false;
    	LinkList* taila = heada;
    	LinkList* tailb = headb;
    	while (taila->next)
    		taila = taila->next;
    	while (tailb->next)
    		tailb = tailb->next;
    	return taila == tailb;
    }

# **13. 求两个单链表相交的第一个节点** #

对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。

对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。  
两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1-len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，知道两个节点的地址相同。

时间复杂度，O(len1+len2)。

//找出两个链表相交的第一个节点
    LinkList* GetFirstCrossNode(LinkList* heada, LinkList* headb) {
    	if (NULL == heada || NULL == headb)
    		return NULL;
    
    	int lengtha = 1;
    	LinkList* taila = heada;
    	while (taila->next) {
    		++lengtha;
    		taila = taila->next;
    	}
    
    	int lengthb = 1;
    	LinkList* tailb = headb;
    	while (tailb->next) {
    		++lengthb;
    		tailb = tailb->next;
    	}
    
    	//两个链表没有相交
    	if (taila != tailb)
    		return NULL;
    
    	LinkList* plong = heada; //指向长度大的链表
    	LinkList* pshort = headb;//指向长度小的链表
    	int diff;
    	if (lengthb > lengtha) {
    		diff = lengthb - lengtha;
    		plong = headb;
    		pshort = heada;
    	}
    
    	//长链表先向前走，使得两个链表对齐
    	for (int i = 0; i < diff; ++i)
    		plong = plong->next;
    
    	while (plong && pshort && plong != pshort) {
    		plong = plong->next;
    		pshort = pshort->next;
    	}
    	return plong;
    }

# **14. 已知一个单链表中存在环，求进入环中的第一个节点** #

首先判断是否存在环，若不存在结束。在环中的一个节点处断开（当然函数结束时不能破坏原链表），这样就形成了两个相交的单链表，求进入环中的第一个节点也就转换成了求两个单链表相交的第一个节点。

//已知链表存在环，求进入链表的第一个节点
    LinkList* GetFirstCircleNode(LinkList* head) {
    	if (NULL == head)
    		return NULL;
    
    	//判断两个链表是否有环，没环返回空
    	LinkList *first = head;
    	LinkList *second = head;
    	while (first && second->next) {
    		first = first->next;
    		second = second->next->next;
    		if (first == second)
    			break;
    	}
    	if (NULL == first || NULL == second->next)
    		return NULL;
    
    	//将相遇时环中的这个节点作为假设的尾节点，
    	//就将原链表变为两个相交的单链表，第一个公共结点即为所求
    	LinkList* assumed_tail = first;
    	LinkList* head1 = head;
    	LinkList* head2 = assumed_tail->next;
    
    	LinkList *pa = head1;
    	int length1 = 1;
    	while (pa != assumed_tail) {
    		pa = pa->next;
    		++length1;
    	}
    
    	LinkList* pb = head2;
    	int length2 = 1;
    	while (pb != assumed_tail) {
    		pb = pb->next;
    		++length2;
    	}
    	pa = head1;
    	pb = head2;
    	if (length1 > length2) {
    		int diff = length1 - length2;
    		while (diff--)
    			pa = pa->next;
    	}
    	else {
    		int diff = length2 - length1;
    		while (diff--)
    			pb = pb->next;
    	}
    	while (pa != pb) {
    		pa = pa->next;
    		pb = pb->next;
    	}
    	return pa;
    }

# **15. 删除某指针指向的结点，时间复杂度O(1)** #

对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点，这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表，链表中的每个节点结构都是一样的，所以我们可以**把该节点的下一个节点的数据复制到该节点，然后删除下一个节点即可**。

要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1)。参考代码如下：

//删除某个指针指向的结点，时间复杂度O(1)
    void DeleteTheNode(LinkList *head, LinkList *to_delete) {
    	if (NULL == to_delete || NULL == head)
    		return;
    
    	//要删除的是最后一个结点
    	if (NULL == to_delete->next) {
    		if (head == to_delete) { //要删除的是链表仅有的一个结点
    			head = NULL;
    			free(to_delete);
    			to_delete = NULL;  //防止垂悬指针
    		}
    		else {             //链表有多个结点，要删除尾结点
    			LinkList* p = head;
    			while (p->next != to_delete)
    				p = p->next;
    			p->next = NULL;
    			free(to_delete);
    			to_delete = NULL;    //防止垂悬指针
    		}
    	} 
    	else { //要删除的不是尾结点
    		LinkList *pnext = to_delete->next;
    		to_delete->value = pnext->value;
    		to_delete->next = pnext->next;
    		free(pnext);
    		pnext = NULL;
    	}
    }

# 16. 部分测试代码 #

int main() {
    
    	/*LinkList *head = BuildList();
    	head = InsertToHead(9, head);
    	head = InsertToTail(100, head);
    	head = DeletebyValue(2, head);
    	printf("length: %d\n", Length(head));
    	PrintList(head);
    	head = Sort(head);
    	printf("list1: ");PrintList(head);*/
    
    	/*head = ReverseList(head);
    	PrintList(head);*/
    
    	/*LinkList* kth = GetRKthNode(head, 1);
    	if (kth)
    	printf("1th：%d\n", kth->value);*/
    
    	/*LinkList *mid = GetMiddleNode(head);
    	if (mid)
    		printf("mid : %d\n", mid->value);*/
    
    	/*RPrintListRecursively(head);
    	printf("\n");
    	RPrintList(head);*/
    
    	//LinkList *head = BuildList();
    	//LinkList *headb = BuildList();
    	//printf("list2: ");PrintList(headb);
    	//LinkList *head_merge = MergeList(head, headb);
    	LinkList *head_merge = MergeListRecursively(head, headb);
    	//printf("list merge: ");PrintList(head_merge);
    
    	/*
    	//LinkList* head = (LinkList*)malloc(sizeof(LinkList));
    	//head->next = head;
    	LinkList *head = BuildList();
    	LinkList *temp = head;
    	while (temp->next)
    		temp = temp->next;
    	temp->next = head;
    	if (HasCircle(head)) {
    		printf("yes\n");
    	}
    	else
    		printf("no\n");*/
    	
    	/*LinkList *head = BuildList();
    	LinkList *temp = head;
    	while (temp->next)
    		temp = temp->next;
    	LinkList* headb = BuildList();
    	temp->next = headb->next->next;
    	LinkList* p = GetFirstCrossNode(head, headb);
    	if (p)
    		printf("%d\n", p->value);*/
    }

完整源码的github地址：[https://github.com/liyangddd/algorithms/blob/master/3list\_none\_head\_node.cpp][https_github.com_liyangddd_algorithms_blob_master_3list_none_head_node.cpp]

参考：

[http://blog.csdn.net/walkinginthewind/article/details/7393134][http_blog.csdn.net_walkinginthewind_article_details_7393134]

[Link 1]: http://blog.csdn.net/u013074465/article/details/44339187
[https_github.com_liyangddd_algorithms_blob_master_3list_none_head_node.cpp]: https://github.com/liyangddd/algorithms/blob/master/3list_none_head_node.cpp
[http_blog.csdn.net_walkinginthewind_article_details_7393134]: http://blog.csdn.net/walkinginthewind/article/details/7393134