题解 | #加油站#

思路: (算法的空间复杂度和时间复杂度都很高，但比较好理解的一种方法) 将每一个加油站看成是一个节点，所有的加油站，就构成了一个环形链表。然后，就以每一个加油站为起点，看是否能绕一圈。(注: 代码中的 HashMap 存放的是，每一个加油站所在的索引) 最后，就能找到最终的结果啦。

import java.util.*;


public class Solution {

    public class ListNode {
        public int index;
        public int gas;
        public int cost;
        public ListNode next;
        ListNode(int index, int gas, int cost) {
            this.index = index;
            this.gas = gas;
            this.cost = cost;
        }
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param gas int整型一维数组
     * @param cost int整型一维数组
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        // write code here

        int len = gas.length;
        HashMap<Integer, ListNode> hashMap = new HashMap<>();
        ListNode head = new ListNode(0, gas[0], cost[0]);
        ListNode node = head;
        hashMap.put(0, head);
        for (int i = 1; i < len; i++) {
            ListNode tmpNode = new ListNode(i, gas[i], cost[i]);
            hashMap.put(i, tmpNode);
            node.next = tmpNode;
            node = tmpNode;
        }
        node.next = head;

        for (int i = 0; i < len; i++) {
            node = hashMap.get(i);
            int hasGas = node.gas;
            hasGas -= node.cost;
            while (hasGas >= 0) {
                node = node.next;

                if (node == hashMap.get(i)) {
                    return i;
                }

                hasGas += node.gas;
                hasGas -= node.cost;
            }
        }
        return -1;
    }
}