高频面试题总结之链表排序

数据结构
数据结构, 高频面试题总结

由于链表数据结构的特殊性，其实基于交换的排序算法已经不适用了，比较适用的是插入排序和归并排序。下面分别展示具体的求解思路。

题目详情

Sort a linked list in O(n log n) time using constant space complexity.

代码

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        
        ListNode midNode = getMid(head);
        ListNode midNext = midNode.next;
        midNode.next = null;
        
        return merge(sortList(head), sortList(midNext));
    }
    
    private ListNode getMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1);
        ListNode curNode = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                curNode.next = head1;
                head1 = head1.next;
            } else {
                curNode.next = head2;
                head2 = head2.next;
            }
            curNode = curNode.next;
        }
        curNode.next = head1 == null ? head2 : head1;
        
        return dummy.next;
    }
}

链表插入排序

题目详情

用插入排序对链表排序

代码：

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
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */
public class Solution {
    /*
     * @param head: The first node of linked list.
     * @return: The head of linked list.
     */
    public ListNode insertionSortList(ListNode head) {
        // write your code here
        //将head中的值都加到该变量后面
        ListNode dummy = new ListNode(0);
        while(head != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < head.val) {
                node = node.next;
            }
            ListNode temp = head.next;
            head.next = node.next;
            node.next = head;
            head = temp;
        }
        return dummy.next;
    }
}
Compartir Comentarios