对单链表进行快速排序_单链表快速排序

public class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
}
1
2
3
4
5
6
7
8

以及一个int类型的值target，当然不是让你在这个单链表中寻找是否存在这个值，要求是让你原地调整这个单链表，使得单链表中节点值val小于target的在左边，等于的在中间，大于的在右边，可以发现这跟快速排序的核心步骤很类似，能实现这个功能，离快速排序就不远了。下面提供思路：
定义6个Node类型的变量：

		Node smallHead = null, smallTail = null;
        Node midHead = null, midTail = null;
        Node bigHead = null, bigTail = null;
1
2
3

见名知意，很好理解，就不解释了，初始都为null，然后遍历单链表head，小于target的往smallTail后面连接，等于target的往midTail后面连接，大于target的往bigTail后面连接，最后让smallTail连接midHead，midTail连接bigHead，完毕，当然处理过程中需要对为null的情况进行判断，举个例子：

head：2->5->3->8->6->5->1     target=5
遍历过后，
smallHead->smallTail : 2->3->1
midHead->midTail : 5->5
bigHead->bigTail : 8->6
最终head变为：2->3->1->5->5->8->6
1
2
3
4
5
6

public class SingleLinkedList {

    public static class Node {
        public int val;
        public Node next;

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

    /**
     * 对head至tail部分进行排序
     * @param head
     * @param tail
     * @return
     */
    public Node quickSort(Node head, Node tail) {
        if (head == null || head.next == tail) {
            return head;
        }
        
        /*****************************partition部分*******************************/
        Node smallHead = null, smallTail = null;
        Node midHead = null, midTail = null;
        Node bigHead = null, bigTail = null;
        Node next;
        int val = head.val;
        while (head != tail) {
            next = head.next;
            if (head.val < val) {
                if (smallHead == null) {
                    smallHead = smallTail = head;
                } else {
                    smallTail.next = head;
                    smallTail = head;
                }
            } else if (head.val == val) {
                if (midHead == null) {
                    midHead = midTail = head;
                } else {
                    midTail.next = head;
                    midTail = head;
                }
            } else if (head.val > val) {
                if (bigHead == null) {
                    bigHead = bigTail = head;
                } else {
                    bigTail.next = head;
                    bigTail = head;
                }
            }
            head.next = null;
            head = next;
        }
        /*****************************partition部分*******************************/

        /********************************连接部分**********************************/
        if (smallHead == null) {
            smallHead = midHead;
        } else {
            smallTail.next = midHead;
            smallHead = quickSort(smallHead, midHead);
        }
        if (bigHead == null) {
            midTail.next = tail;
        } else {
            bigHead = quickSort(bigHead, null);
            midTail.next = bigHead;
            // 找到bigHead的最后一个节点，并连接上之前的tail，防止链表断裂
            if (bigHead != null && tail != null) {
                while (bigHead.next != null) {
                    bigHead = bigHead.next;
                }
                bigHead.next = tail;
            }
        }
        /********************************连接部分**********************************/
        
        return smallHead;
    }
}

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

测试类如下：

import java.util.Arrays;

public class TestSingleLinkedList {
    // 测试次数
    public static final int TIMES = 800000;
    // 元素个数
    public static final int SIZE = 10000;
    // 元素最大值
    public static final int MAX = 10000;
    // 元素最小值
    public static final int MIN = -10000;
    // 辅助数组，用于验证
    public static int[] array;
    // 头节点，游标
    public static SingleLinkedList.Node head, cur;

    public static void main(String[] args) {
        SingleLinkedList sll = new SingleLinkedList();
        for (int i = 0; i < TIMES; i++) {
            init();
            head = sll.quickSort(head, null);
            if (!verify()) {
                System.out.println(head);
                System.out.println("error！");
                System.out.println(Arrays.toString(array));
                break;
            }
        }
        System.out.println(" All test case successfully pass！Accepted！");
    }

    /**
     * 验证
     * @return
     */
    public static boolean verify(){
        cur = head;
        int i;
        Arrays.sort(array);
        for (i = 0; i < SIZE && cur != null; i++, cur = cur.next) {
            if (cur.val != array[i]) {
                return false;
            }
        }
        // 确保经排序后的链表节点个数一致
        return i == SIZE && cur == null;
    }

    /**
     * 初始化，赋值
     */
    public static void init(){
        // 生成[MIN,MAX]之间的随机数
        int val = (int) (Math.random() * (MAX - MIN) + MIN);
        head = new SingleLinkedList.Node(val);
        cur = head;
        array = new int[SIZE];
        array[0] = val;
        for (int i = 1; i < SIZE; i++) {
            val = (int) (Math.random() * (MAX - MIN) + MIN);
            cur.next = new SingleLinkedList.Node(val);
            cur = cur.next;
            array[i] = val;
        }
    }
}

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

笔者经过80万次数的测试，结果都是AC的，验证代码的正确性。