148. 排序链表
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表
这题能通过但是投机取巧了,一般应该不能这样做,直接把节点里的值拿出来,排序后再更新每个节点的值。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
List<Integer> num = new ArrayList<>();
ListNode p = head;
while (p != null) {
num.add(p.val);
p = p.next;
}
Collections.sort(num);
p = head;
int i = 0;
while (p != null) {
p.val = num.get(i);
p=p.next;
i++;
}
return head;
}
}
官方解法太长了,去网上找了另外一个解法。就是归并排序的思想。实际上执行的时间和空间还不如投机取巧的解法,但是这种应该可以面试的时候用
像这种归并排序的递归,连续三个方法都在递归,不知道每次递归的参数是什么,放编译器执行以下真正的归并排序代码,去感受以下迭代是怎么走的。(代码附在最后)
解法来自
https://zhuanlan.zhihu.com/p/434174362
class Solution {
public ListNode sortList(ListNode head) {
//如果链表为空,或者只有一个节点,直接返回即可,不用排序
if (head == null || head.next == null)
return head;
//快慢指针移动,以寻找到中间节点
ListNode slow = head;
ListNode fast = head;
while(fast.next!=null && fast.next.next !=null){
fast = fast.next.next;
slow = slow.next;
}
//找到中间节点,slow节点的next指针,指向mid
ListNode mid = slow.next;
//切断链表
slow.next = null;
//排序左子链表
ListNode left = sortList(head);
//排序左子链表
ListNode right = sortList(mid);
//合并链表
return merge(left,right);
}
public ListNode merge(ListNode left, ListNode right) {
ListNode head = new ListNode(0);
ListNode temp = head;
while (left != null && right != null) {
if (left.val <= right.val) {
temp.next = left;
left = left.next;
} else {
temp.next = right;
right = right.next;
}
temp = temp.next;
}
if (left != null) {
temp.next = left;
} else if (right != null) {
temp.next = right;
}
return head.next;
}
}
归并排序
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = 0; i < k; i++) {
arr[left + i] = temp[i];
}
}
// 测试归并排序
public static void main(String[] args) {
int[] arr = {4, 3, 2, 10, 12, 1, 5, 6};
mergeSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}