链表的基本操作：初始化、创建链表、创建节点、节点插入、节点删除、链表长度、反转链表、是否有环、环的入口、链表置空、链表中间节点

古城微笑少年丶 2023-03-01 12:40 10阅读 0赞

## 链表的基本操作 ##

**链表的初始化**

//链表的结构类型
    struct ListNode { 
    	int m_val;
    	ListNode* m_pNext;
    };
    //这里是没有头指针的情况下的初始化
    ListNode* List_init()
    { 
    	ListNode * pHead = (ListNode*)malloc(sizeof(ListNode));
    	if (pHead == nullptr)
    	{ 
    		printf("创建节点失败");
    		return pHead;
    	}
    	pHead->m_val = 0;
    	pHead->m_pNext = nullptr;
    	return pHead;
    }

**创建一个链表**

void CreateList(ListNode* pHead, int size)
    { 
    	//size为链表的长度
    	//为了保证不改变主调函数内的头指针
    	ListNode* CurrentnNode = (ListNode*)pHead;
    	for (int i = 0; i < size; i++)
    	{ 
    		CurrentnNode->m_val = i;
    		//由于每次赋值后需要创建新的节点，为了保证没有多余的节点
    		if (i < size - 1)
    		{ 
    			//创建节点保存数据
    			CurrentnNode->m_pNext = (ListNode*)malloc(sizeof(ListNode));
    			CurrentnNode = CurrentnNode->m_pNext;
    		}
    	}
    	CurrentnNode->m_pNext = nullptr;
    }

**创建链表的节点**

ListNode* CreateNode(int data)
    { 
    	ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));
    	//在开辟内存时最好一个这样的判断
    	if (pNode == nullptr)
    	{ 
    		printf("创建节点失败");
    		exit(-1);
    	}
    	pNode->m_val = data;
    	pNode->m_pNext = nullptr;
    	return pNode;
    }

**链表节点的插入**

*  第一种方法：在链表的头部插入节点

void AddToFirst(ListNode* pHead, int data)
    { 
    	ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));
    	if (pHead == nullptr)
    	{ 
    		pNode = pHead;
    		pNode->m_pNext = nullptr;
    		pNode->m_val = data;
    	}
    	else
    	{ 
    		pNode->m_pNext = pHead;
    		pNode = pHead;
    	}
    }

*  第二种方法：在链表的尾部插入节点

bool AddToLast(ListNode* pHead, int data)
    { 
    	ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));
    	if (pNode == nullptr)
    	{ 
    		printf("创建节点失败");
    		return false;
    	}
    	if (pHead == nullptr)
    	{ 
    		pNode = pHead;
    	}
    	else
    	{ 
    		ListNode* pTemp = pHead;
    		while (pTemp->m_pNext != nullptr)
    		{ 
    			pTemp = pTemp->m_pNext;
    		}
    		pTemp->m_pNext = pNode;
    	}
    	pNode->m_val = data;
    	pNode->m_pNext = nullptr;
    	return true;
    }

*  第三种方法：在指定位置前插入节点

void AddSpecified(ListNode* pHead, int LocateIndex,int data)
    { 
    	ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));
    	if (pNode == nullptr)
    	{ 
    		printf("创建节点失败");
    		exit(-1);
    	}
    	ListNode* CurrentNode = pHead;
    	int i = 1；
    	//将CurrentNode节点指向插入位置的前一个节点位置（LocateIndex-1）
    	while (CurrentNode && i < LocateIndex - 1)
    	{ 
    		CurrentNode = CurrentNode->m_pNext;
    		i++;
    	}
    	pNode->m_val = data;
    	pNode->m_pNext = CurrentNode->m_pNext;
    	CurrentNode->m_pNext = pNode;
    }

**链表的节点删除**

*  第一种：按照指定元素删除（力扣题）

ListNode* DeleteNode1(ListNode* pHead,int DeleteData)
    { 
    	//虚拟头节点
    	ListNode* pNode = new ListNode();
    	//此时我们操作pCur就可以了
    	ListNode* CurrentNode = pNode;
    	pNode->m_pNext = pHead;
    
    	while (CurrentNode->m_pNext)
    	{ 
    		if (CurrentNode->m_pNext->m_val == DeleteData)
    		{ 
    			CurrentNode->m_pNext = CurrentNode->m_pNext->m_pNext;
    		}
    		else
    		{ 
    			CurrentNode = CurrentNode->m_pNext;
    		}
    	}
    	//最终返回虚拟头结点的next就是新链表的头结点
    	return pNode->m_pNext;
    }

*  第二种：按照指定位置删除

void DeleteNode2(ListNode* pHead, int index)
    { 
    	ListNode* CurrentNode = pHead;
    	int i = 1;
    	while (CurrentNode && i < index - 1)
    	{ 
    		CurrentNode = CurrentNode->m_pNext;
    		i++;
    	}
    	ListNode* DeleteNode;//用来保存将要删除的节点
    	DeleteNode = CurrentNode->m_pNext;
    	CurrentNode->m_pNext = DeleteNode->m_pNext;
    	free(DeleteNode);
    }

**根据给定的元素值返回该值的位置（假设无重复元素）**

int IndexForVal(ListNode * pHead, int val)
    { 
    	int index = 1;
    	ListNode *CurrentNode = pHead;
    	while (CurrentNode)
    	{ 
    		if (CurrentNode->m_val == val)
    		{ 
    			return index; //找到位置返回
    		}
    		CurrentNode = CurrentNode->m_pNext;
    		index++;
    	}
    }

**计算链表的长度**

int Length(ListNode* pHead)
    { 
    	int length = 0;
    	ListNode* CurrentNode = pHead;
    	while (CurrentNode)
    	{ 
    		CurrentNode = CurrentNode->m_pNext;
    		length++;
    	}
    	return length;
    }

**链表的反转**

*  第一种方法：迭代实现链表反转

ListNode* ReverseListNode1(ListNode* pHead)
    { 
    	ListNode* p1 = pHead;
    	ListNode* p2;
    	ListNode* p3;
    	
    	//链表中为空或者链表中只有一个节点，此时不需要逆序
    	if (pHead == nullptr || pHead->m_pNext == nullptr)
    	{ 
    		return pHead;
    	}
    	else
    	{ 
    		//防止链表为空
    		p2 = pHead->m_pNext;
    		while (p2)
    		{ 
    			p3 = p2->m_pNext;
    			p2->m_pNext = p1;
    			p1 = p2;
    			p2 = p3;
    		}
    	}
    	pHead->m_pNext = nullptr;
    	return p1;
    }

*  第二种方法：递归实现链表反转

ListNode* ReverseListNode2(ListNode* pHead)
    { 
    	if (pHead == nullptr || pHead->m_pNext == nullptr)
    	{ 
    		return pHead;
    	}
    	ListNode* NewHead = ReverseListNode2(pHead->m_pNext);
    	pHead->m_pNext->m_pNext = pHead;
    	pHead->m_pNext = nullptr;
    	return NewHead;
    }

**判断链表是否有环**

bool IsListLoop(ListNode* pHead)
    { 
    	ListNode* pFast;	//快指针
    	ListNode* pSlow;	//慢指针
    	pFast = pHead;
    	pSlow = pHead;
    
    	while (pFast!= nullptr && pFast->m_pNext != nullptr)
    	{ 
    		pSlow = pSlow -> m_pNext;
    		pFast = pFast->m_pNext->m_pNext;
    		if (pSlow == pFast)
    			return true;
    	}
    	return false;
    }

**如果链表有环，找到环的入口**

ListNode* FindLoopStart(ListNode* pHead)
    { 
    	ListNode* pFast;	//快指针
    	ListNode* pSlow;	//慢指针
    	pFast = pHead;
    	pSlow = pHead;
    	while (pFast!= nullptr && pFast->m_pNext != nullptr)
    	{ 
    		pSlow = pSlow->m_pNext;
    		pFast = pFast->m_pNext->m_pNext;
    		if (pSlow == pFast)
    			break;
    	}
    	if (pSlow == nullptr || pFast->m_pNext == nullptr)
    		return NULL;
    
    	ListNode* ListNode1 = pHead;	//链表的开始点
    	ListNode* ListNode2 = pSlow;	//相遇点
    
    	while (ListNode1 != ListNode2)
    	{ 
    		ListNode1 = ListNode1->m_pNext;
    		ListNode2 = ListNode2->m_pNext;
    	}
    	return ListNode1;
    }

**链表置空（销毁链表）**

bool DestroyListNode(ListNode* pHead)
    { 
    	ListNode* pNode;
    	ListNode* CurrentNode = pHead;
    	while (CurrentNode)
    	{ 
    		pNode = CurrentNode->m_pNext;
    		free(CurrentNode);
    		CurrentNode = pNode;
    	}
    	pHead->m_pNext = NULL;
    	return true;
    }

**查找链表中间节点（力扣题）**

ListNode* FindMidNode(ListNode* pHead)
    { 
    	ListNode* pFast;
    	ListNode* pSlow;
    	while (pFast != nullptr&&pFast->m_pNext != nullptr)
    	{ 
    		pFast = pFast->m_pNext->m_pNext;
    		pSlow = pSlow->m_pNext;
    	}
    	return pSlow;
    }