排序链表

• 对链表进行归并排序

题目描述

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

示例：

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

C++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }

        ListNode *fast = head->next, *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *mid = slow->next;
        slow->next = nullptr;
        ListNode *h1 = sortList(head);
        ListNode *h2 = sortList(mid);
        return mergeTwoLists(h1, h2);
    }
private:
   ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *p1 = list1, *p2 = list2;
        ListNode *h = nullptr;
        ListNode *p = nullptr;
        while (p1 || p2) {
            ListNode *q = nullptr;
            if (p1 && p2) {
                if (p1->val < p2->val) {
                    q = p1;
                    p1 = p1->next;
                } else {
                    q = p2;
                    p2 = p2->next;
                }
            } else if (p1) {
                q = p1;
                p1 = p1->next;
            } else {
                q = p2;
                p2 = p2->next;
            }

            if (!h) {
                h = q;
                p = q;
            } else {
                p->next = q;
                p = q;
            }
        }
        return h;
    }
};

golang实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

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

    mid := slow.Next
    slow.Next = nil
    left := sortList(head)
    right := sortList(mid)
    return mergeTwoLists(left, right)
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    p1,p2 := list1,list2
    var h,p *ListNode
    for p1 != nil || p2 != nil {
        var q *ListNode
        if p1 != nil && p2 != nil {
            if (p1.Val < p2.Val) {
                q = p1
                p1 = p1.Next
            } else {
                q = p2
                p2 = p2.Next
            }
        } else if p1 != nil {
            q = p1
            p1 = p1.Next
        } else {
            q = p2
            p2 = p2.Next
        }

        // new link list
        if h == nil {
            h = q
            p = q
        } else {
            p.Next = q
            p = q
        }
    }
    
    return h
}