Find Loops In Linkedlist

Find loops in LinkedList

Naive Thinking:用一快一慢两个指针找出是否有loop。着相当于是找圈的起点的简化版。 加强版的见Intersection of Two Linked Lists


算法复杂度O(n)。

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}

public class Solution{

    public static void main(String args[]){
        ListNode l1 = new ListNode(0);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(2);
        l1.next = l2;
        l2.next = l3;
        l3.next = l2;
        Solution s = new Solution();
        System.out.println(s.hasLoop(l1));
    }

    public boolean hasLoop(ListNode head){
        ListNode slow = head, fast = slow;
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
            if(fast==null) break;
            fast = fast.next;
            if(slow==fast) return true;
        }
        return false;
    }
}
 

Vertical Level Traversal of Tree

Print arbitrary binary tree by vertical levels / columns from left to right


example tree

      a
     / \
    b   c
   / \   \
  d   g   z.
   \     /
    e   i
       /
      q
     /
    x
   /
  x1
/
x2


sample output

x2
d x1
b e x.
a g q
c i




Naive Way: 第一想法是一个recursive的算法，给每个节点设置一个weight每次要遍历左节点weight-1，每次遍历右节点weight+1。后来发现recursive的无论是preorder traversal还是DFS都有一个致命问题就是顺序有可能打乱，比如左边的子节点的某一孙子是连续往右拐的，就会优先占据list的第一个。所以这里一定要BFS。不太能recursive。


import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Queue;
import java.util.LinkedList;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
        left = null;
        right = null;
    }
}

public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        int n = 13;
        TreeNode[] tree = new TreeNode[n];
        for(int i = 0;i < n;i++)
            tree[i] = new TreeNode(i);
        for(int i = 0;2*i+2 < n;i++){
            tree[i].left = tree[2*i+1];
            tree[i].right = tree[2*i+2];
        }
          List<List<Integer>> rlst = s.verticalLevelTraversalofTree(tree[0]);
          System.out.println(rlst.size());
          for(int i = 0;i < rlst.size();i++)
              System.out.println(rlst.get(i));
    }

    public List<List<Integer>> verticalLevelTraversalofTree(TreeNode root){
        List<List<Integer>> rlst = new ArrayList<List<Integer>>();
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        Queue<TreeNode> queue= new LinkedList<TreeNode>();
        Map<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>();
        if(root==null){return rlst;}
        // initialize
        queue.add(root);
        weight.put(root,0);
        int min = 0;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            int w = weight.get(node);
            // put into map
            if(!map.containsKey(w)){
                List<Integer> list = new ArrayList<Integer>();
                list.add(node.val);
                map.put(w,list);
            }else{
                List<Integer> list = map.get(w);
                list.add(node.val);
            }
            // enqueue
            if(node.left!=null){
                queue.add(node.left);
                weight.put(node.left,w-1);
            }
            if(node.right!=null){
                queue.add(node.right);
                weight.put(node.right,w+1);
            }
            // update min
            min = Math.min(min,w);
        }
        // generate result
        while(map.containsKey(min)){
            rlst.add(map.get(min++));
        }
        return rlst;
    }

}


Improved Way: 还有一道基于这道题目的问题是
Print the sum of all the numbers at every vertical level in a binary tree
解法一样，可以在得到list后还要求sum，也可以用一个map不断更新同一vertical level的sum。
而且这样一来顺序就不重要了，可以DFS或者preorder traversal什么的， 难度其实降低了。