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

xindoo

发布于 2021-01-22 10:56:40

2710

发布于 2021-01-22 10:56:40

文章被收录于专栏：XINDOO的专栏

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

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

有些人觉得面试面这种题意义不大，谁实际工作中会写过单链表的排序，不都是直接调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 &lt; 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 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 &lt; 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;
        }
    }
}