148.排序链表

给你链表的头结点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); // 创建哑节点，指向原链表头 // 自底向上归并排序 // subLength表示当前要合并的子链表长度 for (int subLength = 1; subLength < length; subLength <<= 1) { // 每次从头开始处理整个链表 ListNode prev = dummyHead; // prev指向已排序部分的末尾 ListNode curr = dummyHead.next; // curr指向待处理部分的头部 // 遍历整个链表，每次处理两个子链表 while (curr != null) { ListNode head1 = curr; // 第一个子链表的头 // 将curr移动到第一个子链表的末尾 for (int i = 1; i < subLength && curr.next != null; i++) { curr = curr.next; } ListNode head2 = curr.next; // 第二个子链表的头 curr.next = null; // 断开第一个子链表 curr = head2; // curr指向第二个子链表的头部 // 将curr移动到第二个子链表的末尾 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; // 将prev移动到合并后链表的末尾 while (prev.next != null) { prev = prev.next; } curr = next; // curr指向剩余未处理的部分 } } return dummyHead.next; } // 合并两个有序链表 public ListNode merge(ListNode head1, ListNode head2) { ListNode dummyHead = new ListNode(0); // 创建哑节点作为合并后链表的头 ListNode temp = dummyHead; // 用于构建新链表的指针 ListNode temp1 = head1; // 遍历第一个链表的指针 ListNode 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; } }