LeetCode経典プログラミング問題(二)

1. sort-list
Description
Sort a linked list in O(n log n) time using constant space complexity.
Solution
idea
O(n log n) means that we can use quick sort or merge sort and so on. The java Collections.sort API sort the list by using merge sort.
Code

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null){
            return head;
        }
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode p = head;
        while(p!=null){
            list.add(p);
            p = p.next;
        }
        Collections.sort(list, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        for(int i = 0; i < list.size(); i++){
            if(i==list.size()-1){
                list.get(i).next = null;
            }else{
                list.get(i).next = list.get(i + 1);
            }
        }
        return list.get(0);
    }
}

2. insertion-sort-list
Description
Sort a linked list using insertion sort.
Solution
idea
Use a list to insert node. We need to save the node.next before an insertion because we will change the node.next during the sorting.

/**
 * 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){
            return null;
        }
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode node = head;
        while(node!=null){
            ListNode curNode = node; 
            node = node.next;
            insertNode(list, curNode);
        }
        return list.get(0);
    }
    private void insertNode(ArrayList<ListNode> list, ListNode node){
        if(list.size() == 0){
            node.next = null;
            list.add(node);
            return;
        }
        if(node.val < list.get(0).val){
            node.next = list.get(0);
            list.add(0,node);
            return;
        }else if(node.val >= list.get(list.size()-1).val){
            list.get(list.size()-1).next = node;
            node.next = null;
            list.add(node);
            return;
        }else{
            for(int i=0;i<list.size();i++){
                if(node.val >= list.get(i).val && node.val <list.get(i + 1).val){
                    list.get(i).next = node;
                    node.next = list.get(i + 1);
                    list.add(i + 1, node);
                    return;
                }
            }
        }
    }
}

3. binary-tree-postorder-traversal
Given a binary tree, return the postorder traversal of its nodes’ values.
For example: Given binary tree{1,#,2,3},

   1
    \
     2
    /
   3

return[3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
Solution
idea

recursive solution - getPostOrder(node.left), getPostOrder(node.right), node

iterative solution - use a stack, push the root into the stack. When we pop a treenode, if the left child and right child of the node are null or has been visited, we pop it. Or we push it into the stack again and push its left child and right child into the stack too.

Code
recursive solution

/**
 * 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> postOrder = new ArrayList();
        getPostOrder(postOrder, root);
        return postOrder;
    }
    public void getPostOrder(ArrayList<Integer> postOrder, TreeNode node){
        if(node==null){
            return;
        }else{
            if(node.left==null&&node.right==null){
                postOrder.add(node.val);
            }else{
                getPostOrder(postOrder, node.left);
                getPostOrder(postOrder, node.right);
                postOrder.add(node.val);
            }
        }
    }
}

iterative solution

/**
 * 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> postOrder = new ArrayList();
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<TreeNode> visited = new ArrayList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null){
                if((node.left==null||visited.contains(node.left))
                   &&(node.right==null||visited.contains(node.right))){
                    postOrder.add(node.val);
                    visited.add(node);
                }else{
                    stack.push(node);
                    stack.push(node.right);
                    stack.push(node.left);
                }
            }
        }
        
        return postOrder;
    }
    
}