题解 | #单链表的排序#
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
<?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 the head node * @return ListNode类 */ function sortInList( $head ) { if($head == null || $head->next == null){ return $head; } // 使用快慢指针找到中间节点 $slow = $head; $fast = $head->next; while($fast != null && $fast->next != null){ $slow = $slow->next; $fast = $fast->next->next; } // 分割成左右两个链表 $newList = $slow->next; $slow->next = null; printf("new: ".$newList->val."\n"); printf($head->val."\n"); // 递归 $left = sortInList($head); $right = sortInList($newList); // 归并排序 $ret = null; $retHead = null; while($left != null && $right != null){ if($left->val <= $right->val){ $temp = new ListNode($left->val); $left = $left->next; }else{ $temp = new ListNode($right->val); $right = $right->next; } if($ret == null){ $ret = $temp; $retHead = $temp; }else{ $ret->next = $temp; $ret = $ret->next; } } // 判断是否有链表剩下 $left == null ? $ret->next = $right : $ret->next = $left; return $retHead; }
方法一:直接把所有链表的值读到array里,用sort,然后再把值放回链表里
方法二:归并排序法(含递归)
- 如果head ==null 或者head->next == null,直接返回head
- 快慢指针法找到链表的中点,根据中点分割成两个链表。注意!!slow = head,fast = head->next,这样才能处理只有两个节点的链表
- 递归分割链表:left = sort(head),right = sort(newHead(右链表的新头))
- 归并排序,左右两个链表合成1个新的有序链表并返回