C++實(shí)現(xiàn)單鏈表按k值重新排序的方法
本文實(shí)例講述了C++實(shí)現(xiàn)單鏈表按k值重新排序的方法。分享給大家供大家參考,具體如下:
題目要求:
給定一鏈表頭節(jié)點(diǎn),節(jié)點(diǎn)值類型是整型。
現(xiàn)給一整數(shù)k,根據(jù)k將鏈表排序?yàn)樾∮趉,等于k,大于k的一個(gè)鏈表。
對(duì)某部分內(nèi)的節(jié)點(diǎn)順序不做要求。
算法思路分析及代碼(C)
思路:將鏈表分為小于k、等于k、大于k的三個(gè)鏈表,然后再合并。
鏈表結(jié)點(diǎn)定義:
typedef struct Node { int data; struct Node* next; }node, *pNode;
算法代碼:
pNode sortLinkedList(pNode head, int k) { pNode sHead = NULL;//小頭 pNode sTail = NULL;//小尾 pNode eHead = NULL;//等頭 pNode eTail = NULL;//等尾 pNode bHead = NULL;//大頭 pNode bTail = NULL;//大尾 pNode temp = NULL; //拆分鏈表 while (head != NULL) { temp = head->next; head->next = NULL; if (head->data < k) { if (!sHead){ sHead = head; sTail = head; } else{ sTail->next = head; sTail = head; } } else if (head->data == k) { if (!eHead){ eHead = head; eTail = head; } else{ eTail->next = head; eTail = head; } } else { if (!bHead){ bHead = head; bTail = head; } else{ bTail->next = head; bTail = head; } } head = temp; } //合并鏈表 if (sTail) { sTail->next = eHead; eTail = (eTail == NULL ? sTail : eTail); } if (eTail) { eTail->next = bHead; } return sHead != NULL ? sHead : (eHead != NULL ? eHead : bHead); }
希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。
相關(guān)文章
C++類結(jié)構(gòu)體與json相互轉(zhuǎn)換
這篇文章主要介紹的是C++類結(jié)構(gòu)體與json相互轉(zhuǎn)換,json字符串一般使用的是開源的類庫(kù)Newtonsoft.Json,方法十分簡(jiǎn)潔,下面就隨小編一起看下面文章內(nèi)容吧2021-09-09C++中基類和派生類之間的轉(zhuǎn)換實(shí)例教程
這篇文章主要介紹了C++中基類和派生類之間的轉(zhuǎn)換,有助于深入理解C++面向?qū)ο蟪绦蛟O(shè)計(jì),需要的朋友可以參考下2014-08-08詳解C++異常處理(try catch throw)完全攻略
這篇文章主要介紹了詳解C++異常處理(try catch throw)完全攻略,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03