LearnFrenzy
Sign in Take a free test

Data Structures in Java · Data Structures in Java Output Questions · Question 17

Where Floyd's pointers meet in a looped list Answer, explanation & discussion

  • Output
  • Hard
  • 0 comments
  • Answer explained
  • Moderated community
Question 17 Back to Exercise

What is the output of the following Java program?

Main.java
public class Main {
    static class Node {
        int val;
        Node next;
        Node(int val, Node next) { this.val = val; this.next = next; }
    }

    static Node meet(Node head) {
        Node s = head, f = head;
        while (f != null && f.next != null) {
            s = s.next;
            f = f.next.next;
            if (s == f) return s;
        }
        return null;
    }

    public static void main(String[] args) {
        Node[] n = new Node[5];
        for (int i = 4; i >= 0; i--) n[i] = new Node(i + 1, i == 4 ? null : n[i + 1]);
        Node m1 = meet(n[0]);
        n[4].next = n[2];                    // 5 -> 3 makes a loop
        Node m2 = meet(n[0]);
        System.out.println((m1 == null) + " " + (m2 == null ? "none" : "meet at " + m2.val));
    }
}
  • A true meet at 3
  • B true meet at 4 Correct
  • C false meet at 5
  • D true none
Correct Answer: Option B

Slow: 2, 3, 4. Fast: 3, 5, then 3 → 4. They meet at 4 – inside the loop, but not necessarily at its start (3).

Discussion & Comments 0

Share your method, a shortcut, or ask about a step you didn't follow.

No comments yet. Be the first to share your solution!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links