链表排序

问题1

在 O(n ^2) 时间复杂度和常数级空间复杂度下，对链表进行排序。

原理

• 回忆一下常用的排序算法，插入算法，冒泡算法，选择算法，快排算法，归并算法，堆排序，希尔排序。 O(n ^2) 的有：插入算法，冒泡算法，选择算法，因此我们可以选择插入算法
• 插入排序，需要两层循环，第一层循环用于处理链表节点；第二层循环用于找到新的链表里比当前节点值要小的位置，记录下pre和next
• 最后，根据上面记录的位置把当前节点插入到pre和next之间，然后reset pre和next。

代码

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode newHead = new ListNode(-1);
        ListNode run = newHead.next;
        ListNode pre = newHead;
        while(head!=null){
            ListNode dump = head;
            head = head.next;
            while(run!=null&&run.val<dump.val){
                pre = run;
                run = run.next;
            }
            
            pre.next = dump;
            dump.next = run;

            pre = newHead;
            run = newHead.next;
        }

        return newHead.next;
    }
}

注意事项

• 设计pre 和 run的时候默认值特别注意：pre=newHead; next = newHead.next;
• 一轮循环完成之后，pre和next需要 reset到原有的值

问题2

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

原理

• 回忆一下常用的排序算法，插入算法，冒泡算法，选择算法，快排算法，归并算法，堆排序，希尔排序。 O(n ^2) 的有：插入算法，冒泡算法，选择算法，因此我们可以选择归并算法
• 归并排序的思想，先做拆分然后在做合并。

代码

class Solution {
    public ListNode sortList(ListNode head) {
        // terminate
        if(head==null||head.next==null){
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = head;
        while(fast!=null&&fast.next!=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        // two linkedlist
        pre.next = null;

       ListNode left =  sortList(head);
       ListNode right =  sortList(slow);

       return merge(left,right);


    }


    private ListNode merge(ListNode left,ListNode right){
        ListNode newHead = new ListNode(-1);
        ListNode run = newHead;

        while(left!=null||right!=null){
            if(left==null){
                run.next = right;
                right = right.next;
            }else if(right==null){
                run.next = left;
                left = left.next;
            }else if(left.val<right.val){
                run.next = left;
                left = left.next;
            }else{
                run.next = right;
                right = right.next;
            }
            run = run.next;
        }
        
        return newHead.next;
    }
}

注意事项

• 先把链表分成两个部分，然后再对两个部分做归并，在归并的过程中，需要注意的是，两个链表分别为空的情况。
• 链表在分为两个链表的时候采用快慢指针的做法，需要注意的是在最后需要操作：把链表分开 pre.next = null;
• 归并排序的思想，先把整体拆分成子问题，然后再对子问题做合并。

问题3

对链表做快速排序

原理

• 迁移数组的快速排序
• 获取到partion位置，然后执行递归
• 获取partion位置: 需要使用两个指针p,q；一遍遍历p和q之间的节点和head节点比较,p到q之前的节点都大于head,p之前的节点都小于head

代码

public class QuickSort {
  private static void quickSort(LinkedNode head, LinkedNode end) {
    if (head == end) {
      return;
    }
    LinkedNode partion = partion(head, end);
    quickSort(head, partion);
    quickSort(partion.next, end);
  }

  private static LinkedNode partion(LinkedNode head, LinkedNode end) {
    LinkedNode p = head;
    LinkedNode q = head.next;
    while (q != end) {
      // 如果q.val<cur change
      if (q.val < head.val) {
        p = p.next;
        int t = q.val;
        q.val = p.val;
        p.val = t;
      }
      q = q.next;
    }
    if (p != head) {
      int t = p.val;
      p.val = head.val;
      head.val = t;
    }

    return p;
  }
}

注意事项

• 先找到partion位置，再注意结束条件
• if (q.val < head.val) {
  p = p.next;
  int t = q.val;
  q.val = p.val;
  p.val = t;
  } 这点比较关键，p = p.next