LeetCode 148. 排序链表
题目
给你链表的头结点head,请将其按升序排列并返回排序后的链表。
思路
思路:归并排序
第一步:切左右,使用快慢指针找到中间节点
第二步:排左右,根据上面找到的中间节点,左右两个链表作为参数递归调用排序方法
第三步:while(leftNode!=null&&rightNode!=null)
判断左右链表的结果,进行归并排序
第四步:对于leftNode!=null / rightNode!=null
,把不为空的节点接到排好序的链表后面
代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {// 归并排序// 返回条件if (head == null) return head;if (head != null && head.next == null) return head;// 切左右ListNode prevSlowNode = head;ListNode slowNode = head;ListNode fastNode = head;while (fastNode != null && fastNode.next != null) {prevSlowNode = slowNode;slowNode = slowNode.next;fastNode = fastNode.next.next;}prevSlowNode.next = null;// 排左右ListNode leftNode = sortList(head); // 排左边ListNode rightNode = sortList(slowNode); // 排右边// 左右归并排序ListNode result = new ListNode(); // dummy headListNode cur = result;while (leftNode != null && rightNode != null) {if (leftNode.val < rightNode.val){cur.next = leftNode;leftNode = leftNode.next;} else {cur.next = rightNode;rightNode = rightNode.next;}cur = cur.next;cur.next = null;}if (leftNode != null){cur.next = leftNode;}if (rightNode != null){cur.next = rightNode;}return result.next;}
}