#yyds干货盘点# leetcode算法题：排序链表

#yyds干货盘点# leetcode算法题：排序链表

题目：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]

输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]

输出：[-1,0,3,4,5]

代码实现：

class Solution { public ListNode sortList(ListNode head) { if (head == null) { return head; } int length = 0; ListNode node = head; while (node != null) { length++; node = node.next; } ListNode dummyHead = new ListNode(0, head); for (int subLength = 1; subLength < length; subLength <<= 1) { ListNode prev = dummyHead, curr = dummyHead.next; while (curr != null) { ListNode head1 = curr; for (int i = 1; i < subLength && curr.next != null; i++) { curr = curr.next; } ListNode head2 = curr.next; curr.next = null; curr = head2; for (int i = 1; i < subLength && curr != null && curr.next != null; i++) { curr = curr.next; } ListNode next = null; if (curr != null) { next = curr.next; curr.next = null; } ListNode merged = merge(head1, head2); prev.next = merged; while (prev.next != null) { prev = prev.next; } curr = next; } } return dummyHead.next; } public ListNode merge(ListNode head1, ListNode head2) { ListNode dummyHead = new ListNode(0); ListNode temp = dummyHead, temp1 = head1, temp2 = head2; while (temp1 != null && temp2 != null) { if (temp1.val <= temp2.val) { temp.next = temp1; temp1 = temp1.next; } else { temp.next = temp2; temp2 = temp2.next; } temp = temp.next; } if (temp1 != null) { temp.next = temp1; } else if (temp2 != null) { temp.next = temp2; } return dummyHead.next; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。