LeetCode 148. Sort List

xiaoxiao2021-02-28  5

问题描述

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

问题分析

用归并排序解答,因为归并排序更容易操纵链表但要求用固定空间,所以必须是归并排序的非递归形式吧

经验教训

如何利用快慢指针找到链表的中间位置,并将它一分为二

代码实现

递归版 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } //将链表一分为二 ListNode slow = head; ListNode fast = head; ListNode tail1 = null; while (fast != null && fast.next != null) { tail1 = slow; slow = slow.next; fast = fast.next.next; } if (tail1 != null) { tail1.next = null; } //分 ListNode l1 = sortList(head); ListNode l2 = sortList(slow); //合 return mergeSortedList(l1, l2); } public ListNode mergeSortedList(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; }else { tail.next = l2; l2 = l2.next; } tail = tail.next; } tail.next = l1 != null ? l1 : l2; return dummy.next; } } 非递归版(以后补充)
转载请注明原文地址: https://www.6miu.com/read-1600011.html

最新回复(0)