Data Structure--单链表相关的具体例题

我就是我 2022-10-29 09:26 42阅读 0赞

# Data Structure #

对于这种题目我们在上一篇博客对接口的实现中大家也了解了很多,我就不多于介绍了,直接讲解执行过程,让大家理解就可以了!!!一起加油

### 删除链表中给定val值的节点 ###

进行遍历链表,找出对应的值,对于要删除的值的位置分为两种,第一个或者是后面的,我们用一个if语句进行分开,其他的元素连接在一起就可以了,不理解的大家可以画表进行理解.

struct ListNode* removeElements(struct ListNode* head, int val){ 
    	//if(head==NULL)
    	// return ;
    
    	struct ListNode* prev = NULL;	//创建一个节点指向尾部
    	struct ListNode* cur = head;	//指向头部
    	while (cur){ 	//循环
    
    		if (cur->val == val){ 	//找到要删除的元素后
    			//非头结点
    			if (prev != NULL){ 	//如果不是头结点
    				prev->next = cur->next;		
    				//这里是直接将要连接节点的地址赋予prev
    			}
    			else{ 
    				//头结点
    				head = cur->next;	//则直接将节点赋予下一个元素
    			}
    			struct ListNode* next = cur->next;	//指向下一个元素
    			free(cur);	//释放空间 
    			cur = next;	//循环
    		}
    		else{ 
    			prev = cur;		//如果没找到则继续循环
    			cur = cur->next;
    		}
    	}
    	return head;	//返回头结点
    }

### 反转单链表 ###

只需要将每一个值遍历的方式进行头插就可以了

struct ListNode* reverseList(struct ListNode* head){ 
    	
    	struct ListNode* newHead = NULL;	//新的头结点
    	struct ListNode* cur = head;		//指向原来的头结点
    	while (cur){ 
    		//头插
    		struct ListNode* next = cur->next;
    		cur->next = newHead;	//指向新的头结点
    		newHead = cur;			
    
    		cur = next;		//循环
    	}
    	return newHead;		//返回新的头结点
    }

### 求中间元素 ###

进两次遍历,第一次遍历出长度,第二次遍历1/2即可

struct ListNode* middleNode(struct ListNode* head){ 
    	
    	struct ListNode* cur = head;	//两个头节点
    	struct ListNode* tmp = head;
    	int len = 0;		//求单链表的长度
    	while (cur){ 
    
    		len++;			//长度
    		cur = cur->next;	//循环
    	}
    	int k = len / 2;		//定义出一半
    	while (k--){ 			//循环
    
    		tmp = tmp->next;	//遍历完即为中间的值,因为只遍历了一半
    	}
    	return tmp;		//返回要求的值
    }

**不同的一种方法**,*快慢方法,创建两个头节点,第一个每次遍历两个,第二个每次遍历一个,这样循环,当第一个头结点遍历完的时候,第二个头结点只遍历了一半,直接将第二个节点返回即可,注意这里遍历的方式是捆绑的,需要进行同时的遍历,所以最后直接输出第二个节点就可以了*但是这种方式是有缺陷的,有一些比较极端的数字无法使用.

struct ListNode* middleNode(struct ListNode* head){ 
    
    	struct ListNode* fast = head;		//快指针
    	struct ListNode* slow = head;		//慢指针
    	while (fast&&fast->next){ 			//循环内同时进行
    
    		fast = fast->next->next;		//每次两个
    		slow = slow->next;				//每次一个
    	}
    	//当快指针遍历完的时候,由于两个语句处于同一个循环中,上面的无法执行下面的也就直接终止了
    	return slow;		//直接返回即可
    }

### 输入链表,输出倒数第K个节点 ###

同样运用快慢指针的方法,**不过这里的是先将第一个头结点遍历K个,在进行两个捆绑的遍历,这是一个规律,大家可以记住,有必要的话像我单链表的接口那篇文章进行画图理解.很简单的**

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) { 
    
    	struct ListNode* fast = pListHead;		//快指针
    	struct ListNode* slow = pListHead;		//慢指针
    
    	while (k--){ 		//先让快循环到K的位置
    		if (fast)
    			fast = fast->next;
    		else
    			return NULL;
    	}
    
    	while (fast){ 
    
    		fast = fast->next;		//再进行捆绑遍历
    		slow = slow->next;
    	}
    	return slow;				//完了直接输出慢节点即可
    }

### 合并两个有序的链表 ###

对于这个题目,我们还是老思路,创建新的头尾节点,现在两个链表中调选一个存放头结点,在进行大小比较运用if语句实现代码,然后将最后一个经过比较但是没有插入进去的节点进行存放,就可以实现整个的代码

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ 
    
    	// if(l1==NULL)
    	// return l2; //判空
    	// if(l2=NULL)
    	// return l1;
    
    	struct ListNode* newHead, *newTail;		//头尾节点
    
    	if (l1->val <= l2->val){ 		//如果l1比较小,就将1作为头结点存放的位置
    
    		newHead = newTail = l1;
    		l1 = l1->next;				//循环
    	}
    	else{ 							//反之则是l2
    
    		newHead = newTail = l2;
    		l2 = l2->next;				//同上
    	}
    	while (l1 && l2){ 				//两个都存在的情况下
    
    		if (l1->val <= l2->val){ 	//如果用的是1
    
    			newTail->next = l1;		//尾部指向l1
    			l1 = l1->next;			//循环
    			newTail = newTail->next;	//循环尾部指向
    		}
    		else{ 						//反之同上
    
    			newTail->next = l2;
    			l2 = l2->next;
    			newTail = newTail->next;
    		}
    	}
    	if (l1)		//如果之后没插入完的是l1,则将最后一个元素插入
    		newTail->next = l1;
    	if (l2)		//反之则是2,具体同上
    		newTail->next = l2;
    
    	return newHead;		//返回新的链表
    }

主要联系的是对于链表的一些基础题目,主要还是一个思路的理解,要多去画图进行理解,这样才能更好的掌握这一部分的题目,大家一起加油,多敲代码!!!新年快乐,恭喜发财!!!