Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the minimum starting gas station’s index if you can travel around the circuit once, otherwise return -1.

You can only travel in one direction. i to i+1, i+2, ... n-1, 0, 1, 2..
Completing the circuit means starting at i and ending up at i again.

Linkedlist Palindrome Algorithm

Problem: Check if a (extra-large) singly linked list of charcters is a palindrome or not.
Solution1:
The brute force algorithm is to revese the linked list and check if the original and reversed linked lists are equal.
Time Complexity: O(n)
Space Compexity: Not good, as it requires an extra linked list.
Solution 2:
1. Find the middle node of the list: This can be done by looping through the list, using two pointers and incrementing the second pointer by 1 only when the first pointer is increamented by two steps. The second pointer would give the middle node of the list, when the first pointer reaches the end of the linked list.
2. Reverse the first half of the linked list.
3. Check if the first half and the second half of the list are equal.
Time Complexity: O(n)
Space Complexity: Better than the first, as we are using only a single linked ist.

If there is a better algorithm, please add to the comments.