单链表的排序问题

单链表的排序问题

作者：Grey

原文地址：

博客园：单链表的排序问题

CSDN：单链表的排序问题

题目链接

LeetCode 148. Sort List

思路一：转换数组结合快速排序

将链表转换成数组，使用快速排序算法，然后把数组排序后的结果还原成链表。

时间复杂度 O(n*logn)，空间复杂度 O(n)。这个思路的核心就是快速排序算法，快速排序算法见如下博客荷兰国旗问题与快速排序算法说明，但是空间复杂度没有达到最优（最优解可以做到空间复杂度O(1)），完整代码如下：

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        int size = 0;
        ListNode cur = head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        ListNode[] nodes = new ListNode[size];
        cur = head;
        int i = 0;
        while (cur != null) {
            nodes[i++] = cur;
            cur = cur.next;
        }
        sortArr(nodes);
        return arrToList(nodes);
    }

    private void sortArr(ListNode[] nodes) {
        p(nodes, 0, nodes.length - 1);
    }

    private void p(ListNode[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] equalArea = netherlandsFlag(arr, L, R);
        p(arr, L, equalArea[0] - 1);
        p(arr, equalArea[1] + 1, R);
    }

    private int[] netherlandsFlag(ListNode[] nodes, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, R};
        }
        int less = L - 1;
        int more = R;
        ListNode num = nodes[R];
        for (int i = L; i < more; i++) {
            if (nodes[i].val < num.val) {
                swap(nodes, ++less, i);
            } else if (nodes[i].val > num.val) {
                swap(nodes, i--, --more);
            }
        }
        swap(nodes, R, more);
        return new int[]{less + 1, more};
    }

    public void swap(ListNode[] nodes, int i, int j) {
        if (i != j) {
            ListNode t = nodes[i];
            nodes[i] = nodes[j];
            nodes[j] = t;
        }
    }

    public ListNode arrToList(ListNode[] nodes) {
        ListNode head = nodes[0];
        ListNode cur = head;
        for (int i = 1; i < nodes.length; i++) {
            cur.next = nodes[i];
            cur = nodes[i];
        }
        cur.next = null;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

思路二：使用归并排序

本题可以利用归并排序算法，在时间复杂度同样为O(n*logn)的情况下，空间复杂度可以达到O(1)，本题参考了归并排序的迭代版本实现，归并排序算法的说明见如下博客与归并排序相关的一些问题。

归并排序的迭代方法，思路如下

设置一个步长，从 1 开始，1，2，4，8，16……2^n 方式递增

每次处理对应步长的链表区间范围内的排序。

步长超过或者等于链表长度，则整个链表排序完成。

比如原始链表为： 1->3->4->2->5->6->4->6->8

先设置步长为 1，链表分成如下区间

[0……1],[2……3],[4……5],[6……7],[8……8]

注：最后一组不够分，则单独作为一组处理。

将如上区间内部排好序，得到的排序后的链表为

1->3,2->4,5->6,4->6,8

然后设置步长为 2，链表分成如下区间

[0……3],[4……7],[8……8]。

然后将上述区间内部先排好序，得到链表为

1->2->3->4,4->5->6->6,8

然后设置步长为 4，链表分成如下区间

[0……7],[8……8]。

然后将上述区间内部先排好序，得到链表为

1->2->3->4->4->5->6->6,8

最后设置步长为 8，链表只有一个区间，直接排序，得到最后结果

1->2->3->4->4->5->6->6->8

完整代码如下

class Solution {
    public  ListNode sortList(ListNode head) {
        int N = 0;
        ListNode cur = head;
        while (cur != null) {
            N++;
            cur = cur.next;
        }
        ListNode h = head;
        ListNode teamFirst = head;
        ListNode pre = null;
        int L = 1;
        while (L < N) {
            while (teamFirst != null) {
                ListNode[] hthtn = hthtn(teamFirst, L);
                ListNode[] mhmt = merge(hthtn[0], hthtn[1], hthtn[2], hthtn[3]);
                if (h == teamFirst) {
                    h = mhmt[0];
                    pre = mhmt[1];
                } else {
                    pre.next = mhmt[0];
                    pre = mhmt[1];
                }
                teamFirst = hthtn[4];
            }
            teamFirst = h;
            pre = null;
            L <<= 1;
        }
        return h;
    }

    public  ListNode[] hthtn(ListNode teamFirst, int len) {
        ListNode ls = teamFirst;
        ListNode le = teamFirst;
        ListNode rs = null;
        ListNode re = null;
        ListNode next = null;
        int p = 0;
        while (teamFirst != null) {
            // 之所以这里是小于等于，是因为这里可能不满足分组的个数（不足个数）
            if (p <= len - 1) {
                le = teamFirst;
            }
            if (p == len) {
                rs = teamFirst;
            }
            if (p > len - 1) {
                re = teamFirst;
            }
            if (p == (len << 1) - 1) {
                break;
            }
            p++;
            teamFirst = teamFirst.next;
        }
        if (le != null) {
            le.next = null;
        }
        if (re != null) {
            next = re.next;
            re.next = null;
        }
        return new ListNode[]{ls, le, rs, re, next};
    }

    // 返回merge后的头和尾
    // 注意边界考虑
    public  ListNode[] merge(ListNode h1, ListNode t1, ListNode h2, ListNode t2) {
        if (h2 == null) {
            return new ListNode[]{h1, t1};
        }
        ListNode head = h1;
        ListNode tail = h1;
        ListNode c = null;
        ListNode pre = null;
        while (h1 != t1.next && h2 != t2.next) {
            if (h1.val > h2.val) {
                c = h2;
                h2 = h2.next;
            } else {
                c = h1;
                h1 = h1.next;
            }
            if (pre == null) {
                // 设置merge后的头节点,赋值给head
                // 后续就由pre去往下插入节点
                pre = c;

                head = c;
            } else {
                pre.next = c;
                pre = c;
            }
        }
        // h1节点没越界
        if (h1 != t1.next) {
            while (h1 != t1.next) {
                pre.next = h1;
                pre = pre.next;
                tail = h1;
                h1 = h1.next;
            }
        } else {
            while (h2 != t2.next) {
                pre.next = h2;
                pre = pre.next;
                tail = h2;
                h2 = h2.next;
            }
        }
        return new ListNode[]{head, tail};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

更多

算法和数据结构笔记