mirror of https://github.com/doocs/leetcode.git
42 lines
1.1 KiB
C#
42 lines
1.1 KiB
C#
/**
|
|
* Definition for singly-linked list.
|
|
* public class ListNode {
|
|
* public int val;
|
|
* public ListNode next;
|
|
* public ListNode(int val=0, ListNode next=null) {
|
|
* this.val = val;
|
|
* this.next = next;
|
|
* }
|
|
* }
|
|
*/
|
|
public class Solution {
|
|
public ListNode SortList(ListNode head) {
|
|
if (head == null || head.next == null) {
|
|
return head;
|
|
}
|
|
ListNode slow = head, fast = head.next;
|
|
while (fast != null && fast.next != null) {
|
|
slow = slow.next;
|
|
fast = fast.next.next;
|
|
}
|
|
ListNode l1 = head, l2 = slow.next;
|
|
slow.next = null;
|
|
l1 = SortList(l1);
|
|
l2 = SortList(l2);
|
|
ListNode dummy = new ListNode();
|
|
ListNode tail = dummy;
|
|
while (l1 != null && l2 != null) {
|
|
if (l1.val <= l2.val) {
|
|
tail.next = l1;
|
|
l1 = l1.next;
|
|
} else {
|
|
tail.next = l2;
|
|
l2 = l2.next;
|
|
}
|
|
tail = tail.next;
|
|
}
|
|
tail.next = l1 != null ? l1 : l2;
|
|
return dummy.next;
|
|
}
|
|
}
|