题目描述

给定一个单链表的头节点 head，请编写一个函数对链表进行排序。排序时，要求只能使用常数级额外空间，也就是说，你不能使用除链表本身以外的其他数据结构来辅助排序。

注意：

• 链表的长度在范围 [0, 5 * 10^4] 内。
• -10^5 <= Node.val <= 10^5

示例

假设链表是 1 -> 4 -> 2 -> 8 -> 3，排序后应为 1 -> 2 -> 3 -> 4 -> 8。

解题思路

由于题目要求只能使用常数级额外空间，我们不能使用归并排序（虽然归并排序对链表排序效率很高，但空间复杂度为 O(n)）。这里我们可以采用自底向上的归并排序（也称为迭代归并排序），每次将链表分割成更小的部分，然后使用归并的思想将相邻的已排序部分合并起来。

PHP 示例代码

<?php
class ListNode {
    public $val = 0;
    public $next = null;

    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function sortList($head) {
    if ($head == null || $head->next == null) {
        return $head;
    }

    $dummy = new ListNode(0);
    $dummy->next = $head;
    $subLength = 1;

    while ($subLength < floor(countNodes($head) / 2) + 1) {
        $prev = $dummy;
        $curr = $dummy->next;

        while ($curr != null && $curr->next != null) {
            $head1 = $curr;
            $tail1 = splitList($head1, $subLength);
            $head2 = $tail1->next;
            $tail2 = splitList($head2, $subLength);

            $merged = mergeLists($head1, $head2);
            $prev->next = $merged;

            while ($prev->next != $tail2) {
                $prev = $prev->next;
            }

            $curr = $tail2;
        }

        $subLength *= 2;
    }

    return $dummy->next;
}

function countNodes($head) {
    $count = 0;
    while ($head != null) {
        $count++;
        $head = $head->next;
    }
    return $count;
}

function splitList($head, $n) {
    $prev = null;
    $count = 0;

    while ($head != null && $count < $n - 1) {
        $prev = $head;
        $head = $head->next;
        $count++;
    }

    if ($prev != null) {
        $prev->next = null;
    }

    return $head;
}

function mergeLists($l1, $l2) {
    $dummy = new ListNode(0);
    $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;
    }

    if ($l1 != null) {
        $tail->next = $l1;
    }

    if ($l2 != null) {
        $tail->next = $l2;
    }

    return $dummy->next;
}
?>

Python 示例代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def sortList(head):
    if not head or not head.next:
        return head

    dummy = ListNode(0)
    dummy.next = head
    sub_length = 1

    while sub_length < len(list(to_list(head))) // 2 + 1:
        prev = dummy
        curr = dummy.next

        while curr and curr.next:
            head1 = curr
            tail1 = split_list(head1, sub_length)
            head2 = tail1.next
            tail2 = split_list(head2, sub_length)

            merged = merge_lists(head1, head2)
            prev.next = merged

            while prev.next != tail2:
                prev = prev.next

            curr = tail2

        sub_length *= 2

    return dummy.next

def to_list(node):
    return [node.val for node in iter(lambda n=node: n if n else None, None)]

def len_list(node):
    length = 0
    while node:
        length += 1
        node = node.next
    return length

def split_list(head, n):
    prev = None
    for _ in range(n - 1):
        prev = head
        head = head.next
    if prev:
        prev.next = None
    return head

def merge_lists(l1, l2):
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 is not None else l2

    return dummy.next

JavaScript 示例代码

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function sortList(head) {
    if (!head || !head.next) return head;

    let dummy = new ListNode(0);
    dummy.next = head;
    let subLength = 1;

    while (subLength < Math.floor(countNodes(head) / 2) + 1) {
        let prev = dummy;
        let curr = dummy.next;

        while (curr && curr.next) {
            let head1 = curr;
            let tail1 = splitList(head1, subLength);
            let head2 = tail1.next;
            let tail2 = splitList(head2, subLength);

            let merged = mergeLists(head1, head2);
            prev.next = merged;

            while (prev.next !== tail2) {
                prev = prev.next;
            }

            curr = tail2;
        }

        subLength *= 2;
    }

    return dummy.next;
}

function countNodes(head) {
    let count = 0;
    while (head) {
        count++;
        head = head.next;
    }
    return count;
}

function splitList(head, n) {
    let prev = null;
    for (let i = 0; i < n - 1 && head; i++) {
        prev = head;
        head = head.next;
    }
    if (prev) prev.next = null;
    return head;
}

function mergeLists(l1, l2) {
    let dummy = new ListNode(0);
    let tail = dummy;

    while (l1 && l2) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }

    tail.next = l1 ? l1 : l2;

    return dummy.next;
}

以上代码展示了如何在 PHP、Python 和 JavaScript 中使用自底向上的归并排序算法对链表进行排序，满足了题目要求的常数级额外空间。