多少人可以在一小时内做出来，面试题插入排序单链表

单元测试 1：
Input: 4->2->1->3
Output: 1->2->3->4

单元测试 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5

有木有空间复杂度要求啊？我 values 抠出来，排好序再拼成一个链表行不行啊？

俺连插入排序是啥都不知道了

10 分钟 算法 101 学的吧

package demo;

class Node {
public Node next;
public int data;

public Node() {
}

public Node(Node next, int data) {
this.next = next;
this.data = data;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node p = this;
while(p!=null) {
sb.append(p.data+"->");
p=p.next;
}
String string = sb.toString();
return string.substring(0,string.length()-2);
}

}

public class Demo {
public static void main(String[] args) {
test1();
test2();
}

private static void test2() {
Node head = new Node(new Node(new Node(new Node(null, 3), 1), 2), 4);
Node sorted = sort(head);
System.out.println(sorted);
}

private static void test1() {
Node head = new Node(new Node(new Node(new Node(new Node(null,0), 4), 3), 5), -1);
Node sorted = sort(head);
System.out.println(sorted);
}

private static Node sort(Node head) {
Node sortedL, sortedR;
sortedL = head;
sortedR = head;
Node current = head;
while (sortedR.next != null) {
current = sortedR.next;
if (current.data < sortedL.data) {
sortedR.next = current.next;
current.next = sortedL;
sortedL = current;
} else if (sortedL.data <= current.data && current.data < sortedR.data) {
Node p = sortedL;
while (p != sortedR) {
if (p.data <= current.data && current.data < p.next.data) {
sortedR.next = curent.next;
current.next = p.next;
p.next = current;
break;
}
p = p.next;
}
} else {
sortedR = current;
}

}
return sortedL;
}
}

这种题目需要一个小时吗。。。。
leetcode easy 难度吧

话说有谁真的写过链表的实现？

@xuanbg 这。。。acm 集训队初级成员也要写的吧。。初期应该是禁 stl 的 所以遇到链表的题必须要手写啊

@xuanbg ？大学数据结构课不用写吗

@ArthurRen 当然大学刚毕业的，或者准备面试的应该可以。但是我想讨论那些在工作岗位上做了几年，但是平时很少用到这样的算法，如果直接让你写，有多少能写出来，天天刷 leetcode 的除外

@tt67wq 应该是 in place 的排序

@AlexLixin 请不要 copy & paste

闭着眼睛写 认识到自己的不足才能进步 不要奢望每个人都这么弱。

知易行难

如果算上搭单元测试的环境而且还用的 C++的话或许会接近一个小时吧。但是这个算法，即使你半路出家一开始没学过数据结构，工作几年还写不出来的话不应该吧。

@xuanbg 链表的实现不是大一基础课教的吗...

链表的插入排序挺好写的啊 我记得 leetcode 做出来没超过 20 分钟

@exonuclease 记错了 是归并排序

@greenlake 我三十多分钟写出来的。比想象中花的时间多，平常不怎么用到的话，细节上不可能不出错。

我觉得给我半个点能写出来…我中午午休试试

easy 难度。多做做 leetcode

2 本毕业一年,得重新学.

应该只能用冒泡排序吧

这个用归并排序, leetcode 就有.插入排序也简单..

半小时

这个算是非常基础的题目了吧，感觉应该要不了一个小时就够了

用 python 的话，就 10 分钟吧

@xuanbg #7 写的话应该基本上都写过吧，不过在生产环境肯定是不会用自己实现的链表的

三点：1.快速指针找到中点 2.归并 3，合并两条有序链表

一个小时，即使你完全没接触过快速排序，拿到算法也应该能自己实现出来了

如果插入的话，没啥难度，归并难点

链表使用一个空的头结点可以简化插入删除操作

插入排序时转变一下思路即可:
数组的插入：前面都是有序的
链表的插入：后面都是有序的

@cjh1095358798 那是归并排序……

这种题在 BAT 这个级别的公司里，应该是技术面第一轮暖身题的难度，最低期望应该是 20 分钟内解决。依次对比可以估算下应该多少人会写

P.S. 当年毕业时某一轮现场面在纸上写了一个完整的 AVL 平衡二叉树，写了 4 页 A4 纸，还跟面试官逐步去纸上调试了一遍，包括各种边界情况

@greenlake 一到公司就迫不及待，花了有半小时吧，写出来了。包含一个编码、测试，用了 Idea 做调试，直接白板写估计够呛。

-------------------
```
import java.util.*;

class Solution {
class Node {
Node next;
int val;

Node() {

}

Node(int val) {
this.val = val;
}

@Override
public String toString() {
return val + (next != null ? "->" + next.toString() : "");
}
}

boolean check(Node head) {
Node p = head.next;

while (p.next != null) {
if (p.val > p.next.val) {
return false;
}
p = p.next;
}

return true;
}

Node asNode(int[] array) {
Node head = new Node();
Node p = head;

for (int e : array) {
p.next = new Node(e);
p = p.next;
}

return head;
}

void sort(Node head) {
if (head == null || head.next == null)
return;

Node prev = head;
Node curr = prev.next;

while (prev.next != null) {
Node p = head;
boolean changed = false;
while (p != curr) {
if (p == head && curr.val < p.next.val || curr.val >= p.val && curr.val < p.next.val) {
prev.next = curr.next;
Node tmp = p.next;
p.next = curr;
curr.next = tmp;
changed = true;
break;
}
p = p.next;
}

if (changed) {
curr = prev.next;
} else {
prev = prev.next;
curr = prev.next;
}
}
}
}


测试：

Solution solution = new Solution();
{
Solution.Node head = solution.asNode(new int[]{5, 1, 5, 3, 4, 2});
solution.sort(head);
assert solution.check(head);
}

{
Solution.Node head = solution.asNode(new int[]{1});
solution.sort(head);
assert solution.check(head);
}

for (int times = 0; times < 1000; times++) {
int len = 2000;
int[] test = new int[len];
Random random = new Random();
for (int i = 0; i < len; i++)
test[i] = random.nextInt();

Solution.Node head = solution.asNode(test);
solution.sort(head);
assert solution.check(head);
}

```

这个不就是链表的遍历+节点插入吗

工作中经常用链表的表示无压力

啥叫插入排序链表？是必须用插入排序，去排一个链表？

@whusnoopy 很凶残，但还是没有手写红黑树凶残哈哈哈哈哈哈哈，旋转真的要写到蛋碎

@jmc891205 方便问下什么工作经常要使用链表呢?

纯手撸要从链表开始撸吧，这个就有点难了。

@Tangdixi 毕业后某年从北京去上海面 Google，去之前 HR 说我们会考察某些内容，比如高级数据结构里有平衡二叉树，可以是 AVL 或者 RB-Tree，我回忆起之前那次蛋疼的 AVL，在去上海的高铁上撸了一遍红黑树，最后在过了南京没到上海的时候终于都调通了，用 C 写的代码，加调试大概 600 行（手动捂脸

不说搞算法了，，大学数据结构也讲队列和链表然后去实现呀