Leetcode刷题java之148. 排序链表

左手的ㄟ右手 2023-07-03 04:43 4阅读 0赞

执行结果：

通过

显示详情

执行用时 :3 ms, 在所有 Java 提交中击败了99.35% 的用户

内存消耗 :39.6 MB, 在所有 Java 提交中击败了82.17%的用户

题目：

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3  
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0  
输出: -1->0->3->4->5

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/sort-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

参考[https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/][https_leetcode-cn.com_problems_sort-list_solution_sort-list-gui-bing-pai-xu-lian-biao-by-jyd]

采用归并排序的思想

代码：

/**
     * 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 fast=head.next;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null)
            {
                slow=slow.next;
                fast=fast.next.next;
            }
            //第二步拆分链表，分别对两个部分进行递归
            ListNode temp=slow.next;
            slow.next=null;
            ListNode left=sortList(head);
            ListNode right=sortList(temp);
            ListNode cur=new ListNode(0);
            ListNode result=cur;
            //递归完毕之后进行合并
            while(left!=null&&right!=null)
            {
                if(left.val<right.val)
                {
                    cur.next=left;
                    left=left.next;
                }else
                {
                    cur.next=right;
                    right=right.next;
                }
                cur=cur.next;
            }
            //如果其中一个为空，就等于另外一个剩下的
            cur.next=left==null?right:left;
            return result.next;
        }
    }

[https_leetcode-cn.com_problems_sort-list_solution_sort-list-gui-bing-pai-xu-lian-biao-by-jyd]: https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/