Data Structure--单链表相关例题(2)

淡淡的烟草味﹌ 2022-10-29 10:29 46阅读 0赞

# 单链表 #

具体接上一篇博客

### 1.找出两个单链表的起始节点 ###

对于这个种题目,我们就还是用两个指针,先对两个单链表进行循环遍历,然后再计算出之间的差值,在将长的那个指针先开始遍历多余的部分,然后再长短指针进行同事的遍历,再将其输出就可以了.

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { 
    	int lenA = 0, lenB = 0;
    	struct ListNode* curA = headA;	//初始定义
    	struct ListNode* curB = headB;
    	while (curA){ 		//循环求长
    
    		++lenA;
    		curA = curA->next;
    	}
    	while (curB){ 		//循环求长
    
    		++lenB;
    		curB = curB->next;
    	}
    
    	int gap = abs(lenA - lenB);
    
    	struct ListNode* longList = headA, *shortList = headB;	//分别指向头结点
    	if (lenB>lenA){ 		//选择语句,对长的进行遍历
    
    		longList = headB;
    		shortList = headA;
    	}
    	while (gap--){ 		//先对长的指向到对应的位置
    
    		longList = longList->next;
    	}
    	while (longList&&shortList){ 		//捆绑循环
    
    		if (longList == shortList)
    			return longList;			//找到相等则返回
    		
    		longList = longList->next;		//继续循环
    		shortList = shortList->next;
    	}
    	return NULL;		//找不到返回空
    }

### 2.给定一个链表，返回链表入环的节点。 若无环，则返回 NULL ###

我们这样理解,定义两个指针,第一个指针比第二个快一个,进行循环遍历,因为是环状的,所以他们总会遇到,由此,就证明遇到了,反之则没有,当找到以后我们又可以进行循环,找到最初开始的那个节点.

struct ListNode* listCycle(struct ListNode* head){ 
    
    	struct ListNode* fast = head;		//两个节点
    	struct ListNode* slow = head;
    	
    	while (fast&&fast->next){ 		//指针捆绑循环
    
    		fast = fast->next->next;
    		slow = slow->next;			//循环
    		
    		if (fast == slow)			//当出现相等返回fast
    			return fast;
    	}
    	return NULL;		//不是循环则返回空
    }
    
    bool hasCycle(struct ListNode *head) { 
    
    	struct ListNode* node = listCycle(head);		//调用
    	if (node){ 		//存在时
    		while (node){ 	//进行循环
    	
    			if (node == head)			//当找到开始节点时,返回值
    				return node;
    			node = node->next;			//未找到继续循环
    			head = head->next;
    		}
    	}
    	return NULL;		//没有则返回空
    }

### 3.对链表进行插入排序 ###

创建了多个节点,插入排序也就是先改变连线的方向,再进行头插即可,注意排序

struct ListNode* insertionSortList(struct ListNode* head){ 
    	//从前向后进行遍历
    	//if(head==NULL||head->head==NULL)
    	// return head;
    
    	struct ListNode* tail, *cur, *prev, *node;
    	
    	tail = head;
    	cur = head->next;
    	while (cur){ 
    
    		if (cur->val<tail->val){ 
    
    			//头结点开始遍历
    			prev == NULL;
    			node = head;
    			while (node && node->val <= cur->val){ 
    
    				prev = node;
    				node = node->next;
    			}
    			tail->next = cur->next;
    			cur->next = node;
    			if (prev)
    				prev->next = cur; 
    			else
    				head = cur;
    			cur = tail->next;
    		}
    		else{ 
    
    			tail = tail->next;
    			cur = tail->next;
    		}
    
    	}
    	return head;
    }

还是对单链表的理解,明天将双向链表,大家一起加油!!!多敲代码!!!