Java LinkedList and Stack Programs for Interviews (With Code)

After strings, arrays and numbers, the next coding-round favourites are linked list and stack programs: reversing a list, detecting a cycle, finding the middle node, checking balanced brackets and building a stack that returns its minimum. Each solution below is short enough to write on paper, with its time complexity. The full collection of programs is in the Java coding programs index.

LinkedList & Stack Problems

// 16. VALID PARENTHESES
boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c=="(' || c=='[' || c=='{") stack.push(c);
        else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c==")' && top!='(") return false;
            if (c=="]' && top!='[") return false;
            if (c=="}' && top!='{") return false;
        }
    }
    return stack.isEmpty();
}

// 17. REVERSE A LINKED LIST (iterative)
Node reverse(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 18. DETECT CYCLE (Floyd's algorithm)
boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

// 19. FIND MIDDLE OF LINKED LIST
Node findMiddle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // slow is at middle
}

// 20. IMPLEMENT STACK USING QUEUES
class MyStack {
    Queue<Integer> q = new LinkedList<>();
    public void push(int x) {
        q.offer(x);
        for (int i = 0; i < q.size()-1; i++)
            q.offer(q.poll());  // rotate to make last first
    }
    public int pop() { return q.poll(); }
    public int top() { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}

More Interview Classics

// 21. FizzBuzz
for (int i=1; i<=100; i++)
    System.out.println(i%15==0?"FizzBuzz":i%3==0?"Fizz":i%5==0?"Buzz":i);

// 22. COUNT WORDS IN STRING
long wordCount(String s) {
    return Arrays.stream(s.trim().split("\\s+")).count();
}

// 23. REMOVE DUPLICATES FROM SORTED ARRAY
int removeDuplicates(int[] nums) {
    if (nums.length==0) return 0;
    int k=1;
    for (int i=1; i<nums.length; i++)
        if (nums[i]!=nums[i-1]) nums[k++]=nums[i];
    return k;
}

// 24. FIND Kth LARGEST ELEMENT
int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int n : nums) {
        minHeap.offer(n);
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.peek();
}

// 25. GROUP ANAGRAMS
List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        String key = new String(arr);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

// 26. LRU CACHE (LinkedHashMap)
class LRUCache extends LinkedHashMap<Integer,Integer> {
    int capacity;
    LRUCache(int cap) {
        super(cap, 0.75f, true);  // accessOrder=true
        this.capacity = cap;
    }
    public int get(int key) { return super.getOrDefault(key, -1); }
    public void put(int key, int value) { super.put(key, value); }
    @Override
    protected boolean removeEldestEntry(Map.Entry e) {
        return size() > capacity;
    }
}

// 27. BINARY SEARCH
int binarySearch(int[] arr, int target) {
    int l=0, r=arr.length-1;
    while (l<=r) {
        int mid = l + (r-l)/2;
        if (arr[mid]==target) return mid;
        if (arr[mid]<target) l=mid+1; else r=mid-1;
    }
    return -1;
}

// 28. POWER OF TWO
boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n-1)) == 0;
}

// 29. MISSING NUMBER (1 to n)
int missingNumber(int[] nums) {
    int n = nums.length;
    int expected = n*(n+1)/2;
    int actual = 0;
    for (int num : nums) actual += num;
    return expected - actual;
}

// 30. LONGEST SUBSTRING WITHOUT REPEATING CHARS (Sliding Window)
int lengthOfLongestSubstring(String s) {
    Map<Character,Integer> map = new HashMap<>();
    int maxLen=0, left=0;
    for (int right=0; right<s.length(); right++) {
        char c = s.charAt(right);
        if (map.containsKey(c) && map.get(c) >= left)
            left = map.get(c) + 1;
        map.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Complexity Cheat Sheet

In Java, prefer ArrayDeque over the legacy Stack class for stack behaviour; mention this in interviews.

FAQs

How do you reverse a linked list in Java?

Walk the list with three references (previous, current, next), pointing each node's next back to the previous node; return the old tail as the new head. It runs in O(n) time and O(1) space.

Should I use Stack or ArrayDeque in Java?

ArrayDeque. The Stack class is synchronized legacy code built on Vector; ArrayDeque is faster and is what the Java documentation recommends for stack and queue use.