题解 | #单链表的排序#
单链表的排序
http://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
1、选择排序，外层循环定位起点，默认为最小值，内层循环一直找后面比当前起点小的值进行交换
注：其实这样做是不好的做法，因为题目的意思是想涉及节点的交换而不是单纯的值交换，但是这样结果也是对的，属于取巧了
public ListNode sortInList (ListNode head) {
// write code here
ListNode pre = head;
while(pre!=null){
ListNode preNext = pre.next;
while(preNext!=null){
if(pre.val>preNext.val){
int temp = pre.val;
pre.val=preNext.val;
preNext.val=temp;
}
preNext=preNext.next;
}
pre=pre.next;
}
return head;
}
2、自底向上归并排序（时间复杂度（nlogn），空间复杂度O（logn))
将链表挨个分组，再（有序链表）合并，分组的办法是用快慢指针，当快指针走到末尾的时候，慢指针正好是一半的位置
public ListNode sortInList (ListNode head) {
//这种情况出现那么就证明当前分组为单个的，那么不需要继续分组了
if(head.next==null){
return head;
}
//慢指针
ListNode slow = head;
//快指针，这里为什么不是head呢？而是head.next呢，
ListNode fast = head.next;
//如果head
// 假设 1，2，3，这样的情况，按照下面的while循环，slow落在2上没问题
// 假设 1，2这样的情况，slow落在2上，那如果要正常分组，slow应该落在1上
//如果head.next
// 假设 1，2，3，这样的情况，按照下面的while循环，slow落在2上没问题,solw落在2上
// 假设 1，2这种情况，slow落在1上
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
//记录slow的落点的下一个，它是右分组的起点
ListNode temp = slow.next;
//断开两段链表
slow.next=null;
slow = temp;
ListNode left = sortInList(head);
ListNode right = sortInList(slow);
//合并两段有序链表
ListNode nodeHeda = new ListNode(-1);
ListNode node = nodeHeda;
while(left!=null&&right!=null){
if(left.val>=right.val){
node.next=right;
right=right.next;
}
else{
node.next=left;
left=left.next;
}
node=node.next;
}
node.next=(left==null? right:left);
return nodeHeda.next;
}
paypal工作强度 6人发布