Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Solution1：stack

思路： 依次push存进stack中，若..则pop
Note： 利用Deque作为stack操作时，操作都在head，pop() == removeFirst()，push() == addFirst()，所以最后遍历Deque(作为stack)时，是从stack顶到stack底，结果需要reverse, 或insert(0, str)
Time Complexity: O(N) Space Complexity: O(N)

Solution2：linkedlist

思路： 依次append存进list中，若..则removeLast
Note： 这样最后遍历Deque(作为list)时，正序即可
Time Complexity: O(N) Space Complexity: O(N)

Solution1 Code：

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<String>();

        // to simplify the result stack by removing redundant path
        for(String str: path.split("/")) {
            if(str.equals("..")) {
                if(!stack.isEmpty()) stack.pop(); // pop() == removeFirst()
            }
            else if(str.equals(".") || str.isEmpty()) continue;
            else stack.push(str);   // push() == addFirst()
        }

        //prepare the result
        StringBuilder result = new StringBuilder("");
        for(String str: stack) result.insert(0, str).insert(0, "/");
        return result.length() == 0 ? "/": result.toString();
    }
}

Solution2 Code：

class Solution {
    public String simplifyPath(String path) {
        Deque<String> list = new LinkedList<>();

        // to simplify the result list by removing redundant path
        for(String str: path.split("/")) {
            if(str.equals("..")) {
                if(!list.isEmpty()) list.removeLast(); 
            }
            else if(str.equals(".") || str.isEmpty()) continue;
            else list.add(str);   
        }

        //prepare the result
        StringBuilder result = new StringBuilder("");
        for(String str: list) result.append("/").append(str);
        return result.length() == 0 ? "/": result.toString();
    }
}