鏈表的常見實現 · 點滴算法

鏈表結點聲明如下： ~~~ struct LinkList { int value; LinkList *next; }; ~~~ **以下是不帶頭結點的單鏈表的操作。** # 1. 根據輸入建立單鏈表將輸入的節點插入到鏈表頭部。 ~~~ //根據輸入建立單鏈表：鏈表頭部插入 LinkList *BuildList() { LinkList *head = NULL; int data; int i = 0; while (scanf("%d", &data) != EOF) { //scanf("%d", &data);++i; LinkList *new_node = (LinkList *)malloc(sizeof(LinkList)); if (NULL == new_node) { fprintf(stderr, "malloc failed"); return head; } new_node->value = data; if (head == NULL) { new_node->next = NULL; head = new_node; } else { new_node->next = head; head = new_node; } } return head; } ~~~ # 2. 鏈表插入操作鏈表插入時注意當鏈表為空的情況。 ### （1）在鏈表頭插入 ~~~ //在鏈表頭部插入節點 LinkList *InsertToHead(int value, LinkList *head) { LinkList *new_node = (LinkList *)malloc(sizeof(LinkList)); if (new_node == NULL) { fprintf(stderr, "malloc failed"); return head; } new_node->value = value; new_node->next = NULL; if (head == NULL) { head = new_node; } else { new_node->next = head; head = new_node; } return head; } ~~~ ### （2）在鏈表尾部插入 ~~~ //鏈表尾部插入節點 LinkList *InsertToTail(int value, LinkList *head) { LinkList *new_node = (LinkList *)malloc(sizeof(LinkList)); if (new_node == NULL) { fprintf(stderr, "malloc failed"); return head; } new_node->value = value; new_node->next = NULL; if (head == NULL) head = new_node; else { LinkList *pnode = head; while (pnode->next != NULL) pnode = pnode->next; pnode->next = new_node; } return head; } ~~~ # 3. 鏈表的刪除操作注意當鏈表僅有一個節點時的刪除。 ~~~ //刪除某節點 LinkList *DeletebyValue(int value, LinkList* head) { if (head == NULL) return head; LinkList *pToDelete = NULL; if (head->value == value) { pToDelete = head; head = head->next; } else { LinkList *p = head; while (p->next != NULL && p->next->value != value) p = p->next; if (p->next != NULL) { pToDelete = p->next; p->next = pToDelete->next; } } if (pToDelete != NULL) { free(pToDelete); pToDelete = NULL; } return head; } ~~~ # 4.?求單鏈表中結點的個數注意檢查鏈表是否為空。時間復雜度為O（n）。該操作不用特意檢查鏈表是否為空，如下代碼，鏈表為空會返回0**。** ~~~ unsigned int Length(LinkList *head) { unsigned int length = 0; LinkList *p = head; while (p) { ++length; p = p->next; } return length; } ~~~ # 5. 打印鏈表元素 ### （1）正向打印鏈表 ~~~ //打印單鏈表 void PrintList(LinkList *head) { LinkList *p = head; while (p) { printf("%d ", p->value); p = p->next; } printf("\n"); } ~~~ ### （2）逆序打印鏈表 ~~~ //逆序打印單鏈表：非遞歸 void RPrintList(LinkList* head) { if (NULL == head) return; stack<int> list_stack; while (head) { list_stack.push(head->value); head = head->next; } while (!list_stack.empty()) { printf("%d ", list_stack.top()); list_stack.pop(); } printf("\n"); } //逆序打印單鏈表：遞歸 void RPrintListRecursively(LinkList* head) { if (NULL == head) return; else { RPrintListRecursively(head->next); printf("%d ", head->value); } } ~~~ # 6.為單鏈表的元素排序由于單鏈表只有通過其next指針才能獲取下一個元素，因此，對單鏈表的排序只能采用向后遍歷的排序方法，例如[冒泡排序的改進](http://blog.csdn.net/u013074465/article/details/44339187)。而不能使用如插入排序、快速排序等需要向前查找的算法。如下算法是用冒泡排序進行的。一趟排序將未排序子序列中最大的元素放到鏈表已經排序子序列的頭部（此最大元素是已排序子序列中的最小值）。 ~~~ //冒泡排序單鏈表 LinkList* Sort(LinkList *head) { if (NULL == head) return head; int length = Length(head); int unorder_size = length; int flag = 1; while (flag) { flag = 0; LinkList *p = head; for (int i = 0; p->next && i < unorder_size; ++i) { if (p->value > p->next->value) { int temp = p->value; p->value = p->next->value; p->next->value = temp; flag = 1; } p = p->next; } --unorder_size; } return head; } ~~~ # 7. 單鏈表的翻轉從頭到尾遍歷原鏈表，每遍歷一個結點，將其摘下放在新鏈表的最前端。注意鏈表為空和只有一個結點的情況。時間復雜度為O（n） ~~~ //翻轉單鏈表 LinkList* ReverseList(LinkList *head) { //其實這里if判斷當鏈表節點個數小于兩個的情況 //不是必須的，因為之后的程序包含這里的判斷 if (NULL == head || NULL == head->next){ return head; } LinkList *reverse_head = NULL; //翻轉后鏈表的頭指針 LinkList *pcurrent = head; //pcurrent遍歷鏈表 while (pcurrent) { LinkList* temp = pcurrent; pcurrent = pcurrent->next; temp->next = reverse_head; reverse_head = temp; } return reverse_head; } ~~~ # 8. 查找單鏈表中的倒數第K個結點（k > 0）最容易想到的方法：先統計單鏈表中結點的個數，然后再找到第（n-k）個結點。注意鏈表為空，k為0，k為1，k大于鏈表中節點個數時的情況。時間復雜度為O（n）。 **另一種思路**：僅需遍歷一次單鏈表。主要思路就是使用兩個指針，先讓前面的指針走到正向第k個結點，這樣前后兩個指針的距離差是k-1，之后前后兩個指針一起向前走，前面的指針走到最后一個結點時，后面指針所指結點就是倒數第k個結點。注意鏈表節點個數小于k的情況。 ~~~ //找出鏈表倒數第k個節點（k > 0) LinkList * GetRKthNode(LinkList *head, int k) { if (k < 1 || NULL == head) return NULL; LinkList *first = head; LinkList *second = head; //如果節點個數小于k返回NULL for (int i = 1; i < k; ++i) { if (second->next) second = second->next; else return NULL; } //兩個指針同時移動，直到快的second指針走到最后一個節點， //此時慢的first指針指向的就是倒數第k個節點 while (second->next != NULL) { first = first->next; second = second->next; } return first; } ~~~ # 9. 查找單鏈表的中間結點此題可用于上一題類似的思想。也是設置兩個指針，只不過這里是，兩個指針同時向前走，前面的指針每次走兩步，后面的指針每次走一步，前面的指針走到最后一個結點時，后面的指針所指結點就是中間結點：第n / 2 + 1個結點。當鏈表元素個數為偶數時，代碼返回的是n/2 + 1個結點，這個應該討論：也許需要返回的是中間兩個節點或者他們的平均值。注意鏈表為空，鏈表結點個數為1和2的情況。時間復雜度O（n）： ~~~ //返回單鏈表的中間節點，當鏈表節點個數為偶數時 //該函數返回鏈表第n/2 + 1個節點 LinkList *GetMiddleNode (LinkList* head) { //鏈表為空或者僅有一個節點 if (NULL == head || NULL == head->next) return head; LinkList *first = head; LinkList *second = head; while (second->next) { first = first->next; second = second->next; if (second->next) { //當節點個數為偶數時情況比較特殊 second = second->next; } } return first; } ~~~ # 10. 合并兩個有序的單鏈表使得合并后鏈表仍有序，如下代碼保留值相同的元素。**** 這個類似歸并排序。尤其注意兩個鏈表都為空的情況，和其中一個為空時的情況。只需要O（1）的空間。時間復雜度為O（max(len1, len2)）。 ~~~ //合并兩個有序的單鏈表：非遞歸 //鏈表原來相等的元素都保留 LinkList* MergeList(LinkList* heada, LinkList *headb) { if (NULL == heada) return headb; if (NULL == headb) return heada; LinkList *head_merge = NULL; //比較第一個節點大小，取小者作為合并后第一個節點 if (heada->value <= headb->value) { head_merge = heada; //注意下面兩條語句順序不能換，否則heada將指向空 heada = heada->next; } else { head_merge = headb; //注意下面兩條語句順序不能換，否則headb將指向空 headb = headb->next; //head_merge->next = NULL; } head_merge->next = NULL; LinkList *pmerge = head_merge; while(heada != NULL && headb != NULL) { if (heada->value <= headb->value) { pmerge->next = heada; heada = heada->next; pmerge = pmerge->next; } else { pmerge->next = headb; headb = headb->next; pmerge = pmerge->next; } pmerge->next = NULL; } if (heada) pmerge->next = heada; else if (headb) pmerge->next = headb; return head_merge; } //合并兩個有序的單鏈表：遞歸 //鏈表原來相等的元素都保留 LinkList* MergeListRecursively(LinkList *heada, LinkList *headb) { if (NULL == heada) return headb; if (NULL == headb) return heada; LinkList *head_merge = NULL; if (heada->value <= headb->value) { head_merge = heada; head_merge->next = MergeListRecursively(heada->next, headb); } else { head_merge = headb; head_merge->next = MergeListRecursively(heada, headb->next); } return head_merge; } ~~~ # 11. 判斷一個單鏈表中是否有環這里也是用到兩個指針。如果一個鏈表中有環，也就是說用一個指針去遍歷，是永遠走不到頭的。因此，我們可以用兩個指針去遍歷，一個指針一次走兩步，一個指針一次走一步，如果有環，兩個指針肯定會在環中相遇。時間復雜度為O（n）。 ~~~ //判斷鏈表中是否有環 bool HasCircle(LinkList *head) { if (NULL == head) return false; LinkList *first = head; LinkList *second = head; while (first && second->next) { second = second->next->next; first = first->next; if (first == second) return true; } return false; } ~~~ # 12. 判斷兩個單鏈表是否相交如果兩個鏈表相交于某一節點，那么在這個相交節點之后的所有節點都是兩個鏈表所共有的。也就是說，如果兩個鏈表相交，那么最后一個節點肯定是共有的。先遍歷第一個鏈表，記住最后一個節點，然后遍歷第二個鏈表，到最后一個節點時和第一個鏈表的最后一個節點做比較，如果相同，則相交，否則不相交。時間復雜度為O(len1+len2)，因為只需要一個額外指針保存最后一個節點地址，空間復雜度為O(1)。 ~~~ //判斷兩個鏈表是否相交 bool IsCross(LinkList* heada, LinkList *headb) { if (NULL == heada || NULL == headb) return false; LinkList* taila = heada; LinkList* tailb = headb; while (taila->next) taila = taila->next; while (tailb->next) tailb = tailb->next; return taila == tailb; } ~~~ # 13. 求兩個單鏈表相交的第一個節點對第一個鏈表遍歷，計算長度len1，同時保存最后一個節點的地址。對第二個鏈表遍歷，計算長度len2，同時檢查最后一個節點是否和第一個鏈表的最后一個節點相同，若不相同，不相交，結束。兩個鏈表均從頭節點開始，假設len1大于len2，那么將第一個鏈表先遍歷len1-len2個節點，此時兩個鏈表當前節點到第一個相交節點的距離就相等了，然后一起向后遍歷，知道兩個節點的地址相同。時間復雜度，O(len1+len2)。 ~~~ //找出兩個鏈表相交的第一個節點 LinkList* GetFirstCrossNode(LinkList* heada, LinkList* headb) { if (NULL == heada || NULL == headb) return NULL; int lengtha = 1; LinkList* taila = heada; while (taila->next) { ++lengtha; taila = taila->next; } int lengthb = 1; LinkList* tailb = headb; while (tailb->next) { ++lengthb; tailb = tailb->next; } //兩個鏈表沒有相交 if (taila != tailb) return NULL; LinkList* plong = heada; //指向長度大的鏈表 LinkList* pshort = headb;//指向長度小的鏈表 int diff; if (lengthb > lengtha) { diff = lengthb - lengtha; plong = headb; pshort = heada; } //長鏈表先向前走，使得兩個鏈表對齊 for (int i = 0; i < diff; ++i) plong = plong->next; while (plong && pshort && plong != pshort) { plong = plong->next; pshort = pshort->next; } return plong; } ~~~ # 14. 已知一個單鏈表中存在環，求進入環中的第一個節點首先判斷是否存在環，若不存在結束。在環中的一個節點處斷開（當然函數結束時不能破壞原鏈表），這樣就形成了兩個相交的單鏈表，求進入環中的第一個節點也就轉換成了求兩個單鏈表相交的第一個節點。 ~~~ //已知鏈表存在環，求進入鏈表的第一個節點 LinkList* GetFirstCircleNode(LinkList* head) { if (NULL == head) return NULL; //判斷兩個鏈表是否有環，沒環返回空 LinkList *first = head; LinkList *second = head; while (first && second->next) { first = first->next; second = second->next->next; if (first == second) break; } if (NULL == first || NULL == second->next) return NULL; //將相遇時環中的這個節點作為假設的尾節點， //就將原鏈表變為兩個相交的單鏈表，第一個公共結點即為所求 LinkList* assumed_tail = first; LinkList* head1 = head; LinkList* head2 = assumed_tail->next; LinkList *pa = head1; int length1 = 1; while (pa != assumed_tail) { pa = pa->next; ++length1; } LinkList* pb = head2; int length2 = 1; while (pb != assumed_tail) { pb = pb->next; ++length2; } pa = head1; pb = head2; if (length1 > length2) { int diff = length1 - length2; while (diff--) pa = pa->next; } else { int diff = length2 - length1; while (diff--) pb = pb->next; } while (pa != pb) { pa = pa->next; pb = pb->next; } return pa; } ~~~ # 15. 刪除某指針指向的結點，時間復雜度O(1) 對于刪除節點，我們普通的思路就是讓該節點的前一個節點指向該節點的下一個節點，這種情況需要遍歷找到該節點的前一個節點，時間復雜度為O(n)。對于鏈表，鏈表中的每個節點結構都是一樣的，所以我們可以把該節點的下一個節點的數據復制到該節點，然后刪除下一個節點即可。要注意最后一個節點的情況，這個時候只能用常見的方法來操作，先找到前一個節點，但總體的平均時間復雜度還是O(1)。參考代碼如下： ~~~ //刪除某個指針指向的結點，時間復雜度O(1) void DeleteTheNode(LinkList *head, LinkList *to_delete) { if (NULL == to_delete || NULL == head) return; //要刪除的是最后一個結點 if (NULL == to_delete->next) { if (head == to_delete) { //要刪除的是鏈表僅有的一個結點 head = NULL; free(to_delete); to_delete = NULL; //防止垂懸指針 } else { //鏈表有多個結點，要刪除尾結點 LinkList* p = head; while (p->next != to_delete) p = p->next; p->next = NULL; free(to_delete); to_delete = NULL; //防止垂懸指針 } } else { //要刪除的不是尾結點 LinkList *pnext = to_delete->next; to_delete->value = pnext->value; to_delete->next = pnext->next; free(pnext); pnext = NULL; } } ~~~ # 16. 部分測試代碼 ~~~ int main() { /*LinkList *head = BuildList(); head = InsertToHead(9, head); head = InsertToTail(100, head); head = DeletebyValue(2, head); printf("length: %d\n", Length(head)); PrintList(head); head = Sort(head); printf("list1: ");PrintList(head);*/ /*head = ReverseList(head); PrintList(head);*/ /*LinkList* kth = GetRKthNode(head, 1); if (kth) printf("1th：%d\n", kth->value);*/ /*LinkList *mid = GetMiddleNode(head); if (mid) printf("mid : %d\n", mid->value);*/ /*RPrintListRecursively(head); printf("\n"); RPrintList(head);*/ //LinkList *head = BuildList(); //LinkList *headb = BuildList(); //printf("list2: ");PrintList(headb); //LinkList *head_merge = MergeList(head, headb); ////LinkList *head_merge = MergeListRecursively(head, headb); //printf("list merge: ");PrintList(head_merge); /* //LinkList* head = (LinkList*)malloc(sizeof(LinkList)); //head->next = head; LinkList *head = BuildList(); LinkList *temp = head; while (temp->next) temp = temp->next; temp->next = head; if (HasCircle(head)) { printf("yes\n"); } else printf("no\n");*/ /*LinkList *head = BuildList(); LinkList *temp = head; while (temp->next) temp = temp->next; LinkList* headb = BuildList(); temp->next = headb->next->next; LinkList* p = GetFirstCrossNode(head, headb); if (p) printf("%d\n", p->value);*/ } ~~~ 完整源碼的github地址：[https://github.com/liyangddd/algorithms/blob/master/3list_none_head_node.cpp](https://github.com/liyangddd/algorithms/blob/master/3list_none_head_node.cpp) 參考： [http://blog.csdn.net/walkinginthewind/article/details/7393134](http://blog.csdn.net/walkinginthewind/article/details/7393134)