首页 > 代码库 > LeetCode Sort List
LeetCode Sort List
Sort a linked list in O(n log n) time using constant space complexity.
归并排序的基本思想是：找到链表的middle节点，然后递归对前半部分和后半部分分别进行归并排序，最后对两个以排好序的链表进行Merge。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { private ListNode getMiddle(ListNode head) { ListNode slow = head,fast=head; while (fast.next!=null&&fast.next.next!=null) { slow=slow.next; fast=fast.next.next; } return slow; } private ListNode merge(ListNode a, ListNode b) { ListNode first=new ListNode(-1); ListNode curr = first; while (a!=null&&b!=null) { if (a.val<=b.val) { curr.next=a; a=a.next; }else { curr.next=b; b=b.next; } curr=curr.next; } if (a!=null) { curr.next=a; }else { curr.next=b; } return first.next; } public ListNode sortList(ListNode head) { if (head==null||head.next==null) { return head; } ListNode middleNode = getMiddle(head); ListNode nextPart = middleNode.next; middleNode.next=null; return merge(sortList(head),sortList(nextPart)); }}
LeetCode Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。