單鏈表的相關操作

1.冒泡排序對單鏈表進行排序

void LinkListBubbleSort(LinkNode* head)
{if(head == NULL){    return;//空鏈表}    if(head -> next == NULL){    return;//只有一個結點}    LinkNode* cur = head;//趟數LinkNode* tail = NULL;//尾指針LinkNode* tmp = head;//次數for(; cur -> next != NULL; cur = cur -> next){    for(tmp = head; tmp -> next != tail; tmp = tmp -> next){    if(tmp -> data > tmp -> next -> data){    LinkNodeSwap(&tmp -> data, &tmp -> next -> data);}                                                                                                                                                }    tail = tmp; }    
}

????其中cur控制總共需要幾趟,N個元素需要N-1趟排序, tmp控制一趟需要進行幾次比較
這里寫圖片描述

2.將兩個已經排好序的單鏈表進行合并,并且保證新鏈表有序

LinkNode* LinkListMerge(LinkNode* head1, LinkNode* head2)
{                                                                                                                                                            if(head1 == NULL){return head2;}if(head2 == NULL){return head1;}LinkNode* new_head;LinkListInit(&new_head);LinkNode* cur1 = head1;LinkNode* cur2 = head2;while(cur1 != NULL && cur2 != NULL){if(cur1 -> data > cur2 -> data){LinkListPushBack(&new_head, cur1 -> data);cur1 = cur1 -> next;}else{LinkListPushBack(&new_head, cur2 -> data);cur2 = cur2 -> next;}}while(cur2 != NULL){LinkListPushBack(&new_head, cur2 -> data);cur2 = cur2 -> next;}while(cur1 != NULL){LinkListPushBack(&new_head, cur1 -> data);cur1 = cur1 -> next;}return new_head;
}

????假設待排序列如下圖
這里寫圖片描述
????那就創建一個新鏈表,將其初始化,每次將cur1 和 cur2 作比較,在保證 cur1 和 cur2 兩個指針都不為空的前提下將它們兩個中 data 小的插入到新鏈表的尾部就可以同時 cur1 和 cur2 往后移動,當 cur1 為空, cur2 不為空時就將 cur2 的剩下的所有元素依次全部搬到新鏈表中.
這里寫圖片描述

3.查找單鏈表中間結點,并且保證只能遍歷一次鏈表


LinkNode* LinkListFindMid(LinkNode* head)
{if(head == NULL){return NULL;}if(head -> next == NULL || head -> next -> next == NULL){return head;}LinkNode* fast = head;LinkNode* slow = head;while(fast != NULL && fast -> next != NULL){fast = fast -> next -> next;slow = slow -> next;                                                                                                                                 }return slow;
}

????定義兩個指針 fas t, slow ,在保證 fast 不為空并且 fast -> next 不為空的前提下,讓 fast 一次走兩步,slow一次走一步, 當 fast 走到空的時候 slow 就剛好處于中間,此時返回 slow 就可以了
這里寫圖片描述
????????????????

4.找鏈表的倒數第 k 個結點

LinkNode* LinkListFindLastKNode(LinkNode* head, int K)
{if(head == NULL){return NULL;//空鏈表}int count = 0;LinkNode* cur = head;while(cur != NULL){count ++;cur = cur -> next;}if(K > count){return NULL;//K值大于節點個數}LinkNode* slow = head;LinkNode* fast = head;int i = 0;for(; i < K; i ++){                                                                                                                                                        if(fast != NULL){fast = fast -> next;}}while(fast != NULL){slow = slow -> next;fast = fast -> next;}return slow;
}

????同樣,定義兩個指針, fast 和 slow, 讓 fast 先走 k 步, 然后 fas 走一步,slow跟著走一步,當 fast 等于空的時候 slow 剛好是倒數第 k 個結點
這里寫圖片描述

????????????????

4.刪除鏈表的倒數第 k 個結點

void LinkListEraseLastKNode(LinkNode** phead, int K)
{if(phead == NULL){return;//非法輸入}if(*phead == NULL){                                                                                                                                                        return;//空鏈表}int count = 0;LinkNode* cur = *phead;while(cur != NULL){count++;cur = cur -> next;}if(K > count){return;//K大于結點個數}if(K == count){LinkListPopFront(phead);return;}LinkNode* to_delete = LinkListFindLastKNode(*phead, K + 1);LinkListEraser(phead, to_delete -> next);
}

????利用前面的算法找到倒數第 k + 1個結點, 然后刪除第 k + 1 個結點的下一個結點即可
這里寫圖片描述

5.約瑟夫環問題

LinkNode* LinkListJosephCircle(LinkNode** phead, int M)
{if(phead == NULL){                                                                                                                                                          return NULL;//非法輸入}if(*phead == NULL){return NULL;//鏈表為空}if((*phead) -> next == *phead){return *phead;//只有一個元素}LinkNode* cur = *phead;LinkNode* to_delete;int i = 0;while(cur -> next != cur){for(i = 1; i < M; i ++){cur = cur -> next;}cur -> data = (cur -> next) -> data;to_delete = cur -> next;cur -> next = to_delete -> next;LinkNodeDestroy(&to_delete);}return cur;
}

????對于約瑟夫環問題先將這個鏈表形成一個帶環的鏈表,即最后一個結點的 next 指向第一個結點,然后從第一個結點遍歷這個鏈表,當遍歷到第M個結點時就把這個結點刪除,注意當給定目標是M是,指針移動M - 1次, 當指針移動M-1次時,就定義一個指針to_delete指向要刪除的這個元素,然后刪除這個元素,如此繼續,直到剩余一個結點,即cur -> next = cur 時,就返回這個結點
????????????? 這里寫圖片描述

6.逆序打印單鏈表

void LinkListReversePrint(LinkNode* phead)
{if(phead == NULL) {return;}                                                                                                                                                           LinkListReversePrint(phead -> next);printf("%c   ", phead -> data);
}

????對于逆序打印單鏈表,采用遞歸的思想,即讓指針往后遍歷整個鏈表,直到最后一個時再將其對應的 data 打印出來即可
這里寫圖片描述

7.單鏈表的逆置

void LinkListReverse(LinkNode** phead)
{if(phead == NULL){    return;//非法輸入}    if(*phead == NULL){    return;//鏈表為空}    if((*phead) -> next == NULL){    return;//只有一個元素}    LinkNode* cur = *phead;LinkNode* to_delete = cur; while(cur -> next != NULL){    to_delete = cur -> next;cur -> next = to_delete -> next;to_delete -> next = *phead;*phead = to_delete;                                                                                                                                    }    
}

???? 這里寫圖片描述

8.判斷鏈表是否有環

LinkNode* LinkListHasCircle(LinkNode* head)
{if(head == NULL)                                                                                                                                           {    return NULL;//空鏈表}    if(head -> next == NULL){    return NULL;//一個結點并且無環}    LinkNode* fast = head;LinkNode* slow = head;while(fast != NULL && fast -> next != NULL){    fast = fast -> next -> next;slow = slow -> next;if(slow == fast){    return slow;}    }    return NULL;
}

????先構造一個有環的鏈表,然后定義兩個指針 fast 和 slow, 在保證 fast 不為空, 以及fast -> next 不為空的前提下,fast一次走兩步,slow一次走一步,如果有環,在一定時間內 fast 一定會追上 slow ,即 fast = slow,當遇到 fast 為空時,那就說明沒有環
?????????????????? 這里寫圖片描述

9.求環的長度

int LinkListGetCircleLength(LinkNode* head)
{if(head == NULL){    return 0;//空鏈表}    if(head -> next == NULL){    return 0;//只有一個結點，沒有環}    LinkNode* meet = LinkListHasCircle(head);LinkNode* slow = meet;int size = 0; while(slow -> next != meet){    size ++;slow = slow -> next;}    return size + 1; 
}

????定義一個快指針fast,一個慢指針slow,fast一次走兩步, slow一次走一步,當兩者相遇時定義一個指針meet記住這個位置, 然后讓slow繼續往前走,同時定義一個計數器進行計數count,當slow的next等于meet時候,此時count+1便是換的長度
????????????????? 這里寫圖片描述

10.求環的入口點

LinkNode* LinkListGetCircleEntry(LinkNode* head)
{if(head == NULL){    return NULL;//空鏈表                                                                                                                                   }    if(head -> next == NULL){    return NULL;//只有一個結點，并且沒有環}    LinkNode* meet = LinkListHasCircle(head);if(meet == NULL){    return NULL;}    LinkNode* slow = head;LinkNode* fast = meet;while(slow != fast){    slow = slow -> next;fast = fast -> next;}    return slow;
}

????還是快慢指針,鏈表開始到環入口的距離等于快慢指針相遇點到環入口的距離,即定義一個指針fast等于快慢指針相遇的那個位置,再定義一個指針slow等于head,然后兩個指針一次向后遍歷,當fast = slow 的之后,返回這個位置,便是環入口的位置
???????????????????? 這里寫圖片描述

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/384109.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/384109.shtml
英文地址，請注明出處：http://en.pswp.cn/news/384109.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！