链表排序 · Sort List

［抄题］：

［思维问题］：

［一句话思路］：

［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

quick sort 整体－局部（先找大小值，再局部递归） 里面不稳定 最坏n2, 最好 平均 nlgn  数组空间复杂度1（内部操作即可）

merge sort 局部－整体（先局部操作完，最后全部merge到一起） 里面稳定  数组空间复杂度n（需要新建数组）

［一刷］：

1. 快慢指针的条件是 fast.next != null && fast. != null,  因为一次挪动了2步，要预防后面没有数。
2. ListNode的返回类型一定要用新的tail指针。只对dummy操作，最后返回dummy.next的时候就变了。一个个点添加时，需要tail = tail.next;之后的操作都对下一个点进行 
3. tail.next = head1;剩余的一次性添加，加一次就行了 用if
4. 有了tail之后，dummy.next = head1是多此一举，可以删除
5. merge时只需要保证head1 head2插入时本身非空即可
6. 每个函数里都要判空，包括merge函数
7. 用left right节点来表示左右merge的结果

［总结］：

［复杂度］：Time complexity: O(n log n) Space complexity: O(1)

［英文数据结构，为什么不用别的数据结构］：

［其他解法］：

［Follow Up］：

［题目变变变］：

// version 1: Merge Sortpublic 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

［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

1. 返回类型是void，直接对dummy操作就行了
2. dummy,corner case第一步就写 中间的连接符号是||
3. 最开始的ListNode newHead = null;
4. 不用返回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);    }}