链表排序 · Sort List
［抄题］：
［思维问题］：
［一句话思路］：
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
quick sort 整体－局部（先找大小值，再局部递归） 里面不稳定 最坏n2, 最好 平均 nlgn 数组空间复杂度1（内部操作即可）
merge sort 局部－整体（先局部操作完，最后全部merge到一起） 里面稳定 数组空间复杂度n（需要新建数组）
［一刷］：
- 快慢指针的条件是 fast.next != null && fast. != null, 因为一次挪动了2步，要预防后面没有数。
- ListNode的返回类型一定要用新的tail指针。只对dummy操作，最后返回dummy.next的时候就变了。一个个点添加时，需要tail = tail.next;之后的操作都对下一个点进行
- tail.next = head1;剩余的一次性添加，加一次就行了 用if
- 有了tail之后，dummy.next = head1是多此一举，可以删除
- merge时只需要保证head1 head2插入时本身非空即可
- 每个函数里都要判空，包括merge函数
- 用left right节点来表示左右merge的结果
［总结］：
［复杂度］：Time complexity: O(n log n) Space complexity: O(1)
［英文数据结构，为什么不用别的数据结构］：
［其他解法］：
［Follow Up］：
［题目变变变］：
// version 1: Merge Sort
public class Solution {
private ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
} private ListNode merge(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
tail.next = head1;
head1 = head1.next;
} else {
tail.next = head2;
head2 = head2.next;
}
tail = tail.next;
}
if (head1 != null) {
tail.next = head1;
} else {
tail.next = head2;
} return dummy.next;
} public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
} ListNode mid = findMiddle(head); ListNode right = sortList(mid.next);
mid.next = null;
ListNode left = sortList(head); return merge(left, right);
}
}
链表重排reorder list
［抄题］：
给定一个单链表L: L0→L1→…→Ln-1→Ln,
重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2→…
必须在不改变节点值的情况下进行原地操作。
［思维问题］：
后半部分的顺序倒过来了，要用reverse，没想到
［一句话思路］：
找中点－逆序－merge
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- 返回类型是void，直接对dummy操作就行了
- dummy,corner case第一步就写 中间的连接符号是||
- 最开始的ListNode newHead = null;
- 不用返回dummy.next，可以随意对dummy操作。
［总结］：
［复杂度］：Time complexity: O() Space complexity: O()
［英文数据结构，为什么不用别的数据结构］：
［其他解法］：
［Follow Up］：
［题目变变变］：
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/ public class Solution {
/*
* @param head: The head of linked list.
* @return: nothing
*/
//findMiddle
private ListNode reverse(ListNode head) {
if (head == null) {
return null;
}
ListNode newHead = null;
while(head != null) {
ListNode temp = head.next;
head.next = newHead;
newHead = head;
head = temp;
}
return newHead;
} private ListNode findMiddle(ListNode head) {
if (head == null) {
return head;
}
ListNode fast = head.next;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
//merge
private void merge(ListNode head1,ListNode head2) {
ListNode dummy = new ListNode(0);
int index = 0; while(head1 != null && head2 != null) {
if (index % 2 == 0) {
dummy.next = head1;
head1 = head1.next;
}
else {
dummy.next = head2;
head2 = head2.next;
}
dummy = dummy.next;
index++;
}
if (head1 != null) {
dummy.next = head1;
}
if (head2 != null) {
dummy.next = head2;
} //return dummy.next;
}
//reverse //reorder
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return ;
}
ListNode mid = findMiddle(head);
ListNode right = reverse(mid.next);
mid.next = null;
merge(head,right);
}
}