当前位置：首页 > news >正文

数据结构---单链表（常见的复杂操作）

news 来源：原创 2024/9/20 7:11:53

一、单链表

1.1.查找中间元素

1.2.查找倒数第K个节点

1.3.链表倒置

1.4.冒泡排序

1.5.选择排序

1.6.环，确认有环单链表的环入口和环大小

二、总结

一、单链表

1.1.查找中间元素

定义两个指针，分别指向第一个元素，第一个指针每次向后遍历两个节点，第二个指针向后遍历一个节点，最终当第一个指针遍历到最后一个时，第二个也就刚好指向中间节点。

LinkList *FindMidLinkList(LinkList *phead)
{LinkList *pfast = NULL;LinkList *pslow = NULL;if (phead->pnext == NULL){return NULL;}pfast = pslow = phead->pnext;while (pfast != NULL){pfast = pfast->pnext;if (NULL == pfast){break;}pfast = pfast->pnext;if (NULL == pslow){break;}pslow = pslow->pnext;}return pslow;}

1.2.查找倒数第K个节点

定义两个指针，分别指向头节点，先让第一个指针向后遍历k次，让两个指针之间相差k个位置，然后让他们一起向后遍历，直到第一个指针指向最后一个节点，此时第二个指针就指向倒数第k个位置。

LinkList *FindTailKLinkList(LinkList *phead, int k)
{   LinkList *pfast = NULL;LinkList *pslow = NULL;if (phead->pnext == NULL){return NULL;}pfast = phead;pslow = phead;for (int i = 0; i < k; i++){pfast = pfast->pnext;if (pfast == NULL){break;}}if (pfast == NULL){return phead;}while (pfast != NULL){pfast = pfast->pnext;pslow = pslow->pnext;}return pslow;}

1.3.链表倒置

将链表的数据链与头节点分开，然后依次头插法插入头节点后面，完成倒置

int HeadInvertLinkList(LinkList *phead)
{LinkList *ptmp = NULL;LinkList *qtmp = NULL;ptmp = phead->pnext;phead->pnext = NULL;qtmp = ptmp;while(qtmp != NULL){qtmp = qtmp->pnext;ptmp->pnext = phead->pnext;phead->pnext = ptmp;ptmp = qtmp;}return 0;
}

1.4.冒泡排序

int BulleSortLinkList(LinkList *phead)
{LinkList *ptmp1 = NULL;LinkList *ptmp2 = NULL;LinkList *qtmp = NULL;DataType data = 0;//链表只有头节点或只有一个数据节点,不需要排序if (phead->pnext == NULL || phead->pnext->pnext == NULL){return 0;}ptmp1 = phead->pnext;ptmp2 = phead->pnext->pnext;while (1){ptmp1 = phead->pnext;ptmp2 = phead->pnext->pnext;if (ptmp2 == qtmp){break;}while (ptmp2 != qtmp){if (ptmp1->data < ptmp2->data){data = ptmp1->data;ptmp1->data = ptmp2->data;ptmp2->data = data;}ptmp1 = ptmp1->pnext;ptmp2 = ptmp2->pnext;}qtmp = ptmp1;}return 0;}

1.5.选择排序

int SelectSortLinkList(LinkList *phead)
{LinkList *ptmp1 = NULL;LinkList *ptmp2 = NULL;LinkList *qtmp = NULL;DataType data = 0;//链表只有头节点或只有一个数据节点,不需要排序if (phead->pnext == NULL || phead->pnext->pnext == NULL){return 0;}qtmp = phead->pnext;while (qtmp->pnext != NULL){ptmp1 = qtmp;ptmp2 = qtmp->pnext;while(ptmp2 != NULL){if (ptmp2->data < ptmp1->data){ptmp1 = ptmp2;}ptmp2 = ptmp2->pnext;}if (ptmp1 != qtmp){data = ptmp1->data;ptmp1->data = qtmp->data;qtmp->data = data;}qtmp = qtmp->pnext;}}

1.6.环，确认有环单链表的环入口和环大小

定义两个指针，分别指向第一个元素，第一个指针每次向后遍历两个节点，第二个指针向后遍历一个节点，可以保证两个指针的差程自然数增长，这样两个指针终会在环里相遇。

LinkNode *IsHasCircle(LinkNode *pHead, int *pcnt)
{LinkNode *pFast = NULL;LinkNode *pSlow = NULL;LinkNode *pTmpNode = NULL;LinkNode *pNode1 = NULL;LinkNode *pNode2 = NULL;int ret = 0;int cnt = 1;pSlow = pFast = pHead->pNext;while (1){pFast = pFast->pNext;if (NULL == pFast){ret = 0;break;}pFast = pFast->pNext;if (NULL == pFast){ret = 0;break;}pSlow = pSlow->pNext;if (pSlow == pFast){ret = 1;break;}}if (1 == ret){//获得环长pTmpNode = pSlow->pNext;while (pTmpNode != pSlow){cnt++;pTmpNode = pTmpNode->pNext;}*pcnt = cnt;//获得环入口位置pNode1 = pSlow;pNode2 = pHead->pNext;while (1){pNode1 = pNode1->pNext;pNode2 = pNode2->pNext;if (pNode1 == pNode2){return pNode1;}}}return NULL;
}