#yyds干货盘点# LeetCode 腾讯精选练习 50 题：排序链表

2 years ago

source link: https://blog.51cto.com/u_13321676/5843913
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

#yyds干货盘点# LeetCode 腾讯精选练习 50 题：排序链表

精选原创

灰太狼_cxh 2022-11-11 11:42:49 博主文章分类：leetcode ©著作权

文章标签 i++ 链表代码实现 文章分类 Java 编程语言 阅读数353

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

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

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

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

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

输入：head = []

输出：[]

代码实现：

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;
}
}