编辑代码



import java.util.*;

public class FindFirstNode {
    public static class Node {
        private Integer id;
        private Integer nextId;
        public Node(Integer id, Integer nextId) {
            this.id = id;
            this.nextId = nextId;
        }
        @Override
        public String toString() {
            return String.format("Node(id:%d; nextId:%d)", id, nextId);
        }
    }

    public static int findFirstNode(ArrayList<Node> list){
        if(list==null || list.size()==0) {
            return 0;
        }
        HashMap<Integer,Integer> nodeMap = new HashMap<>();
        for(Node node : list) {
           Integer value = nodeMap.get(node.id);
           if(value!=null) {
              nodeMap.put(node.id,++value);
           } else {
              nodeMap.put(node.id,1);
           }
           Integer nextIdValue = nodeMap.get(node.nextId);
           if(nextIdValue!=null) {
               nodeMap.put(node.nextId,--nextIdValue);
           } else {
               nodeMap.put(node.nextId,-1);
           }
        }
        int count = 0;
        int result = 0;
        Iterator<Map.Entry<Integer, Integer>> its = nodeMap.entrySet().iterator();
        while(its.hasNext()) {
            Map.Entry<Integer,Integer> entry = its.next();
            if(entry.getValue() == 1) {
                result = entry.getKey();
                count++;
            }
        }
        if(count == 1) {
            return result;
        } else {
            //如果不是只有一个key为1的值,说明可能刚好是环,可能有多个头结点或者是链表不连续
            return -1;
        }

    }

    public static void main(String[] args) {
        ArrayList<Node> list = new ArrayList<>();
        list.add(new Node(2, 3));
        list.add(new Node(3, null));
        list.add(new Node(1, 2));
        System.out.println(findFirstNode(list));
    }
}