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

不念不忘少年蓝@ 2021-09-24 19:06 205阅读 0赞

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

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

有些人觉得面试面这种题意义不大，谁实际工作中会写过单链表的排序，不都是直接调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.  合并两个有序的单链表；  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center]  
    如图所示，红色为未排序链表，蓝色为排序后的链表，红色部分从上往下是拆分的过程，蓝色部分从上往下是合并的过程。 代码实现如下：

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;
        }
    }

## 快排 ##

快排整体的思路和归并差不多，都是拆分、递归、合并，但其拆分就要比归并的拆分策略复杂些。在上文归并算法中，我们只是简单将链表按奇偶变化拆分成了两个链表，但快排的拆分需要选择一个节点作为基准值，比它小的拆到左链表，反之的拆到右链表，然后递归对左右两个链表排序，最后合并。但它的合并就简单了，只需要 左链表+基准节点+又链表简单拼接在一起就可以了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 1]

如图所示，黄色为我选中的基准节点(链表的头节点)，红色为未排序链表，蓝色为排序后的链表，红色部分从上往下是拆分的过程，蓝色部分从上往下是合并的过程。具体代码实现如下：

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 链表题][leetcode top100]
2.  排序相关：第k大的数，上文中快排可能出现的问题以及如何解决?(提示下，如果输入数据全为降序会怎么样)
3.  归并：用一台2g内存的机器排序10个1g的文件。

> 欢迎关注我的面试专栏[面试题精选][Link 1]，**永久免费 持续更新**，本专栏会收集我遇到的比较经典面试题，除了提供详尽的解法外还会从面试官的角度提供扩展题，希望能帮助大家找到更好的工作。另外，也征集面试题，如果你遇到了不会的题 私信告诉我，有价值的题我会给你出一篇博客。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/dddd86630e0d41b2b3a835edb4a05dcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210923/8420465300b54e54af016fb63fc5238b.png
[leetcode top100]: https://leetcode.com/problemset/top-100-liked-questions/
[Link 1]: https://blog.csdn.net/xindoo/category_9991116.html