leetCode 148 排序链表

题目描述：

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例输入输出：

思路：

归并排序

• 利用归并排序，首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。
• 参数：
  • 链表头节点head
• 流程：
  • 通过快慢指针找到链表中间节点mid
  • 归并流程：
    • 结束条件：
      • 判断tempList的长度是否等于nums.length如果是，将tempList加入结果集，结束递归。
    • 要做的事：
      • 建立一个for循环：
        • 将nums的每个元素分别加入temp中。
        • 如果元素位置的visited已被标记为true，遍历下一个。
        • 没有被标记，则在visited标记此数。
        • tempList加入此数。
        • 递归。
        • 将visited的标记去掉。
        • 从temp中将此数移除。
• 复杂度分析：
  • 时间复杂度：O（n*n！）
  • 空间复杂度：O（n）
• 代码：

• /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode() {}
  *     ListNode(int val) { this.val = val; }
  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  * }
  */
  class Solution {
  public ListNode sortList(ListNode head) {
      if (head == null || head.next == null)
          return head;
      ListNode fast = head.next, slow = head;
      while (fast != null && fast.next != null) {
          slow = slow.next;
          fast = fast.next.next;
      }
      ListNode tmp = slow.next;
      slow.next = null;
      ListNode left = sortList(head);
      ListNode right = sortList(tmp);
      ListNode h = new ListNode(0);
      ListNode res = h;
      while (left != null && right != null) {
          if (left.val < right.val) {
              h.next = left;
              left = left.next;
          } else {
              h.next = right;
              right = right.next;
          }
          h = h.next;
      }
      h.next = left != null ? left : right;
      return res.next;
  }
  }