关于java:面试题精选单链表排序也能玩出花来

明天国庆节，祝大家中秋节高兴，顺便给大家拜个早年[狗头]。不过最近还在筹备面试的同学们不要浪太狠，还是要好好学习的鸭。

单链表的排序在数据结构类的面试题中几乎是集大成者，什么排序、链表、链表删除、增加…… 都能体现在单链表排序上，也十分考验候选者的编程基本功，思路说起来很简略，但能不能写进去又是另外一回事了。

有些人感觉面试面这种题意义不大，谁理论工作中会写过单链表的排序，不都是间接调 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 个局部。

1. 把链表分成两个链表；
2. 别离对两个链表排序(能够递归做归并)；
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 个关键词 单链表、排序、归并，基本上下一题都是这三个词的发散，这里我说下我能够发散出的题目。

1. 单链相干的题，曾经烂大巷了，具体参考 leetcode top100 链表题
2. 排序相干：第 k 大的数，上文中快排可能呈现的问题以及如何解决?(提醒下，如果输出数据全为降序会怎么样)
3. 归并：用一台 2g 内存的机器排序 10 个 1g 的文件。

欢送关注我的面试专栏面试题精选，永恒收费 继续更新，本专栏会收集我遇到的比拟经典面试题，除了提供详尽的解法外还会从面试官的角度提供扩大题，心愿能帮忙大家找到更好的工作。另外，也征集面试题，如果你遇到了不会的题 私信通知我，有价值的题我会给你出一篇博客。