LeetCode-in-All
148. Sort List
Medium
Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 104]. -105 <= Node.val <= 105
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Solution
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
public function sortList($head) {
$sortArray = [];
$sortedHead = $head;
while (!is_null($sortedHead)) {
$sortArray[] = $sortedHead->val;
$sortedHead = $sortedHead->next;
}
unset($sortedHead);
sort($sortArray);
$newHead = $head;
for ($i = 0; $i < count($sortArray); $i++) {
$newHead->val = $sortArray[$i];
$newHead = $newHead->next;
}
unset($newHead);
return $head;
}
}