力扣递归 两道简单题合成一道中等题之148. 排序链表

标签：力扣 head ListNode val 148 next 链表 return null

递归归并排序，先找到终点，再合并两个链表

 

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

 

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

/**  * 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) {         return mergeSort(head);
    }
    ListNode mergeSort(ListNode head) {         if (head == null || head.next == null) {             return head;         }         ListNode mid = findMid(head);         ListNode listNodeRight = mergeSort(mid.next);         mid.next = null;         ListNode listNodeLeft = mergeSort(head);         return merge(listNodeLeft, listNodeRight);     }
    ListNode findMid(ListNode head) {         if (head == null) {             return head;         }         ListNode slow = head;         ListNode fast = head.next;         while (fast != null && fast.next != null) {             slow = slow.next;             fast = fast.next.next;         }         return slow;     }
    ListNode merge(ListNode listNode1, ListNode listNode2) {         if (listNode1 == null) {             return listNode2;         } else if (listNode2 == null) {             return listNode1;         } else if (listNode1.val < listNode2.val) {             listNode1.next = merge(listNode1.next, listNode2);             return listNode1;         } else {             listNode2.next = merge(listNode1, listNode2.next);             return listNode2;         }
    } }     /**  * 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 || head.next == null) {             return head;         }         ListNode mid = findMid(head);         ListNode listNodeRight = sortList(mid.next);         mid.next = null;         ListNode listNodeLeft = sortList(head);         return merge(listNodeLeft, listNodeRight);     }
    ListNode findMid(ListNode head) {         if (head == null) {             return head;         }         ListNode slow = head;         ListNode fast = head.next;         while (fast != null && fast.next != null) {             slow = slow.next;             fast = fast.next.next;         }         return slow;     }
    ListNode merge(ListNode listNode1, ListNode listNode2) {         if (listNode1 == null) {             return listNode2;         } else if (listNode2 == null) {             return listNode1;         } else if (listNode1.val < listNode2.val) {             listNode1.next = merge(listNode1.next, listNode2);             return listNode1;         } else {             listNode2.next = merge(listNode1, listNode2.next);             return listNode2;         }
    } }

标签：力扣,head,ListNode,val,148,next,链表,return,null
From： https://www.cnblogs.com/JavaYuYin/p/18012588