LeetCode148. 排序链表-Java&Go-归并排序

• 算法
  • 1.归并排序
  • 2.分割链表为两半
    • 使用快慢指针分割的同时，记录慢指针前一个节点，用于切断左右两部分连接
  • 3.递归排序左右两半链表，然后做merge

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; // 切断左右两部分连接

    ListNode l = sortList(head);
    ListNode r = sortList(slow);
    return mergeList(l, r);
}

private ListNode mergeList(ListNode left, ListNode right) {
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    while (left != null && right != null) {
        if (left.val <= right.val) {
            curr.next = left;
            left = left.next;
        } else {
            curr.next = right;
            right = right.next;
        }
        curr = curr.next;
    }
    if (left == null) {
        curr.next = right;
    } else {
        curr.next = left;
    }
    return dummy.next;
}

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    prev, slow, fast := &ListNode{}, head, head
    for fast != nil && fast.Next != nil {
        prev, slow, fast = slow, slow.Next, fast.Next.Next
    }
    prev.Next = nil

    l := sortList(head)
    r := sortList(slow)
    return mergeList(l, r)
}

func mergeList(left, right *ListNode) *ListNode {
    dummy := &ListNode{Val: -1}
    curr := dummy
    for left != nil && right != nil {
        if left.Val <= right.Val {
            curr.Next = left
            left = left.Next
        } else  {
            curr.Next = right
            right = right.Next
        }
        curr = curr.Next
    }
    if left == nil {
        curr.Next = right
    } else {
        curr.Next = left
    }
    return dummy.Next
}