Sort List
Sort a linked list in O(n log n) time using constant space complexity.
今天并没有写出通过测试的代码...
写了一个冒泡排序的，效率明显不够
明天试试快速和归并
对于数组来说，常用的排序方法有7种
- 插入排序（直接插入和希尔）
- 选择排序（简单选择，堆）
- 交换排序（冒泡，快速）
- 归并排序
推广到链表，应该很多都可以做到
花点时间将基本能看到的方法全部写一遍
package Sort.List;
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
/*
* Sort a linked list in O(n log n) time using constant space complexity.
*/
public ListNode sortList(ListNode head) {
maopaoList(head);
return null;
}
/*
* 冒泡排序，先写思路
* 先判断进来的节点是否为空，是则返回null
* 之后判断进来节点的next字段是否为空，为空返回head
* 之后顺次交换链表中乱序的相邻组合，设置flag，从开头到结尾都
* 一旦发生交换，则设为false，说明有交换，可能仍然是乱序
* 直到某次从头到尾的扫描都没有发生交换
* 则说明已经完成了排序，时间复杂度o(n^2）
* 稳定排序
* 测试结果..当然是Time Limit Exceeded
*/
public ListNode maopaoList(ListNode head){
if(head == null)
return null;
if(head.next == null )
return head;
boolean flag = false;
ListNode firstNode , temp , preNode;
while(true){
flag = true;
//确定第一个节点
if(head.val > head.next.val){
firstNode = head.next ;
preNode = head.next;
temp = head.next.next;
head.next.next = head;
head.next = temp;
}else{
firstNode = head;
preNode = head;
head = head.next;
}
while(head.next != null){
if(head.val > head.next.val){
temp = head.next.next;
preNode.next = head.next;
head.next.next = head;
head.next = temp;
preNode = preNode.next;
flag = false;
}else{
preNode = head;
head = head.next;
}
}
if(flag)
break;
head = firstNode;
}
//print(firstNode);
return firstNode;
}
/*
* 类似归并排序的方法
* 首先让每相邻的2个节点有序，即 1-2，3-4，5-6，。。。。。
* 对每相邻的两段有序的节点归并，使得相邻的两段整个有序；
* 重复2），直到整个链表有序；
* 时间复杂度o(n*logn)
*
* 思路和上面的基本一致
*
*/
public ListNode guibingList(ListNode head){
if(head == null)
return null;
if(head.next == null)
return head;
//明天再战
return null;
}
public void print(ListNode head){
while(head != null){
System.out.print(head.val + " ");
head = head.next;
}
}
public Solution(ListNode head){
sortList(head);
}
public static void main(String[] args){
ListNode first = new ListNode(8);
ListNode second = new ListNode(7);
ListNode third = new ListNode(4);
ListNode fourth = new ListNode(9);
first.next = second;
second.next = third;
third.next = fourth;
Solution test = new Solution(first);
}
}
