2019.7.20刷题记录

Sort a linked list in O(n log n) time using constant space complexity.Sort a linked list in O(n log n) time using constant space complexity.Sort a linked list in O(n log n) time using constant space complexity.要求时间复杂度O(nlogn） 空间复杂度O(1),考虑归并排序

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode mid = getMid(head);
        ListNode next = mid.next;
        mid.next = null;
        return sort(sortList(head) , sortList(next));//将两个已经有序的再排序
    }
    public ListNode getMid(ListNode node){
        if(node == null || node.next == null){
            return node;
        }
        //快慢指针找中间节点
        ListNode fast = node;
        ListNode slow = node;
        while(slow.next != null && fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public ListNode sort(ListNode n1 , ListNode n2){
        ListNode Head = new ListNode(0);
        ListNode cur = Head;
        ListNode cur1 = n1;
        ListNode cur2 = n2;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
            }else{
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        cur.next = cur1 == null ? cur2 : cur1;
        return Head.next;
    }
}

Sort a linked list using insertion sort.使用插入排序对链表排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ArrayList<ListNode> list = new ArrayList<ListNode>();
        while(head != null){
            list.add(head);
            head = head.next;
        }
        for(int i = 1;i < list.size();i++){
            for(int j = i - 1;j >= 0 && list.get(j).val > list.get(j+1).val;j--){
                int temp = list.get(j).val;
                list.get(j).val = list.get(j+1).val;
                list.get(j+1).val = temp;
            }
        }
        return list.get(0);
    }
}

Given a binary tree, return the postorder traversal of its nodes' values.后序的

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root == null){
            return list;
        }
        help(root , list);
        return list;
    }
    public void help(TreeNode root , ArrayList<Integer> list){
        if(root.left != null){
            help(root.left , list);
        }
        if(root.right != null){
            help(root.right , list);
        }
        list.add(root.val);
    }
}