今天國慶節，祝大家中秋節快樂，順便給大家拜個早年[狗頭]，不過最近還在準備面試的同學們不要浪太狠，還是要好好學習的鴨，
單鏈表的排序在資料結構類的面試題中簡直是集大成者，什么排序、鏈表、鏈表洗掉、添加…… 都能體現在單鏈表排序上，也非常考驗候選者的編程基本功，思路說起來很簡單，但能不能寫出來又是另外一回事了，
有些人覺得面試面這種題意義不大，誰實際作業中會寫過單鏈表的排序，不都是直接調Collections.sort()嗎？ 是，沒錯 是這樣，也許對某些人而言，他會這道題和不會這道題對將來的作業產生不了任何影響，這就需要非常長的時間去驗證了，顯然招聘者等不了那么久，他們只想花最少的時間找到你的上限，摸到你的上限后他們就可以簡單假設這條線下面的其他東西你都會了，雖然這種假設有局限性，會讓那種恰巧準備了的人占了便宜，但這種方法卻不失為成本最低的方法，這就好比高考一樣，高考所考的內容大多數人一輩子都用不上，但高考仍有存在的意義，
扯遠了，回到正題，單鏈表排序設計到的知識點都是大學本科資料結構里講過的，所以對應屆生而言這題完全不會超綱，對面試官而言，你能解釋清楚思路 說明你在校資料結構學的還可以，你再能把你思路寫出來，就能向面試官證明你編程能力可以， (這里有個面試小技巧：知道思路不會寫，先把思路給面試官講一遍，你考數學寫個解：還能得0.5分呢)
單鏈表排序可以用哪些排序演算法？ 我的回答是所有排序演算法都可以用，但有些排序會相對簡單些，本文我給出三種(選擇、快排、歸并)方法，剩余的幾種排序演算法有興趣你可以自己實作下，當然有些可能會比較繁瑣，是時候挑戰下自己了[狗頭]，這里我簡化下題目，節點值為int整數，然后鏈表按增序排列，
這里先給出單鏈表節點類
public class LinkedNode {
public int val;
public LinkedNode next;
public LinkedNode() {
this(-1);
}
public LinkedNode(int val) {
this.val = val;
}
}
選擇排序
選擇排序的思路也很簡單，每次從原鏈表中摘掉最小的一個節點，拼接到新鏈表中，直到原鏈表摘干凈，
public class SelectSort implements SortStrategy {
@Override
public LinkedNode sort(LinkedNode head) {
LinkedNode vHead = new LinkedNode(-1);
vHead.next = head;
// 增加虛擬頭節點,方便操作,否則就需要用一堆if來判斷了,代碼會比較啰嗦
LinkedNode newHead = new LinkedNode(-1);
LinkedNode tail = newHead; // tail指向新鏈表的末尾
// 每次從鏈表中摘出來最小的節點,拼接到新鏈表末尾
while (vHead.next != null) {
LinkedNode pre = vHead;
LinkedNode cur = head;
LinkedNode min = head;
LinkedNode minPre = vHead;
// 先遍歷找最小的節點,記錄下最小節點和它前面一個節點
while (cur != null) {
if (cur.val < min.val) {
minPre = pre;
min = cur;
}
pre = cur;
cur = cur.next;
}
// 把min節點從原鏈表中摘除,并拼接到新鏈表中
tail.next = min;
tail = tail.next;
minPre.next = min.next;
}
return newHead.next;
}
}
歸并
我個人感覺歸并其實是最適合做單鏈表排序的演算法，雖然代碼稍微長有些，但思路清晰、好理解，而且時間復雜度只有O(nlogn)，歸并的思路可以分為3個部分，
- 把鏈表分成兩個鏈表；
- 分別對兩個鏈表排序(可以遞回做歸并)；
- 合并兩個有序的單鏈表；
如圖所示，紅色為未排序鏈表，藍色為排序后的鏈表，紅色部分從上往下是拆分的程序，藍色部分從上往下是合并的程序， 代碼實作如下：
public class MergeSort implements SortStrategy {
@Override
public LinkedNode sort(LinkedNode head) {
// 遞回邊界,如果有鏈表只有一個節點就沒必要排序了
if (head == null || head.next == null) {
return head;
}
// 新建了個頭節點方便處理,否則就需要很多if來判斷了
LinkedNode l1 = new LinkedNode();
LinkedNode l2 = new LinkedNode();
LinkedNode p1 = l1;
LinkedNode p2 = l2;
LinkedNode p = head;
// 將原鏈表一分為二,奇數編號節點在l1,偶數編號在l2
while (p != null) {
LinkedNode pnn = null;
if (p.next != null) {
pnn = p.next.next;
}
p1.next = p;
p1 = p1.next;
if (p.next != null) {
p2.next = p.next;
p2 = p2.next;
p2.next = null;
}
p1.next = null;
p = pnn;
}
// 遞回將兩個鏈表做歸并排序.
l1 = sort(l1.next);
l2 = sort(l2.next);
// 合并兩個排序好的有序鏈表
return merge(l1, l2);
}
// 合并兩個有序鏈表
private LinkedNode merge(LinkedNode l1, LinkedNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
LinkedNode newHead = new LinkedNode();
LinkedNode p = newHead;
LinkedNode p1 = l1;
LinkedNode p2 = l2;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
while (p1 != null) {
p.next = p1;
p1 = p1.next;
p = p.next;
}
while (p2 != null) {
p.next = p2;
p2 = p2.next;
p = p.next;
}
return newHead.next;
}
}
快排
快排整體的思路和歸并差不多，都是拆分、遞回、合并，但其拆分就要比歸并的拆分策略復雜些，在上文歸并演算法中，我們只是簡單將鏈表按奇偶變化拆分成了兩個鏈表，但快排的拆分需要選擇一個節點作為基準值，比它小的拆到左鏈表，反之的拆到右鏈表，然后遞回對左右兩個鏈表排序，最后合并，但它的合并就簡單了，只需要 左鏈表+基準節點+又鏈表簡單拼接在一起就可以了，
如圖所示，黃色為我選中的基準節點(鏈表的頭節點)，紅色為未排序鏈表，藍色為排序后的鏈表，紅色部分從上往下是拆分的程序，藍色部分從上往下是合并的程序，具體代碼實作如下：
public class QuickSort implements SortStrategy {
@Override
public LinkedNode sort(LinkedNode head) {
if (head == null || head.next == null) {
return head;
}
LinkedNode left = new LinkedNode();
LinkedNode right = new LinkedNode();
LinkedNode p1 = left;
LinkedNode p2 = right;
LinkedNode p = head.next;
LinkedNode base = head; // 選取頭節點為基準節點
base.next = null;
// 剩余節點中比基準值小就放left里,否則放right里,按照大小拆分為兩條鏈表
while (p != null) {
LinkedNode pn = p.next;
p.next = null;
if (p.val < base.val) {
p1.next = p;
p1 = p1.next;
} else {
p2.next = p;
p2 = p2.next;
}
p = pn;
}
// 遞回對兩條鏈表進行排序
left.next = sort(left.next);
right.next = sort(right.next);
// 先把又鏈表拼到base后面
base.next = right.next;
// 左鏈表+基準節點+右鏈表拼接,左鏈表有可能是空,所以需要特殊處理下
if (left.next != null) {
p = left.next;
// 找到左鏈表的最后一個節點
while (p.next != null) {
p = p.next;
}
// 把base拼接到左鏈表的末尾
p.next = base;
return left.next;
} else {
return base;
}
}
}
面試題擴展
面試官也是要偷懶的，他們也懶得想題，再加上人的思維是具有連續性的，這就意味著大概率下一道面試題(如有)會和這道題相關，我總結這道題可以擴展的3個關鍵詞單鏈表、排序、歸并，基本上下一題都是這三個詞的發散，這里我說下我可以發散出的題目，
- 單鏈相關的題，已經爛大街了，具體參考leetcode top100 鏈表題
- 排序相關：第k大的數，上文中快排可能出現的問題以及如何解決?(提示下，如果輸入資料全為降序會怎么樣)
- 歸并：用一臺2g記憶體的機器排序10個1g的檔案，
歡迎關注我的面試專欄面試題精選，永久免費 持續更新，本專欄會收集我遇到的比較經典面試題，除了提供詳盡的解法外還會從面試官的角度提供擴展題，希望能幫助大家找到更好的作業，另外，也征集面試題，如果你遇到了不會的題 私信告訴我，有價值的題我會給你出一篇博客，
本文來自https://blog.csdn.net/xindoo
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/146024.html
標籤：Java
上一篇：請幫我看一段程式
下一篇：Python例外處理