148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

//利用归并排序的思想
class Solution {     public ListNode sortList(ListNode head) {         if (head == null || head.next == null)             return head;         ListNode prev = null;         ListNode slow = head;         ListNode fast = head;         while (fast != null && fast.next != null ) {             prev = slow;             slow = slow.next;             fast = fast.next.next;         }                  prev.next = null;//将前半段链表设置为null结尾，链表被分成(head,p),(slow,fast)                  ListNode l1 = sortList(head);         ListNode l2 = sortList(slow);                  return merge(l1, l2);     }          private ListNode merge(ListNode l1, ListNode l2) {         ListNode l = new ListNode(0);//设置辅助节点         ListNode p = l;         while (l1 != null && l2 != null) {             if (l1.val < l2.val) {                 p.next = l1;                 l1 = l1.next;             } else {                 p.next = l2;                 l2 = l2.next;             }             p = p.next;//要把p向前移动         }         if (l1 != null)             p.next = l1;         if (l2 != null)             p.next = l2;         return l.next;     } }

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。