CODEWITHSUNDEEP
javalinked-list
yenyen
yenyen

Reputation: 35

how to return the second smallest key in a symbol table

how do I return the second smallest key in a linked list? I've browsed and didn't see a discussion that really helped me.

public class LinkedListST<Key extends Comparable<Key>, Value> {
    private Node first;      // the linked list of key-value pairs

    // a helper linked list data type
    private class Node {
        private Key key;
        private Value val;
        private Node next;

    public Node(Key key, Value val, Node next)  {
        this.key  = key;
        this.val  = val;
        this.next = next;
    }
}

public Key secondMinKey () {
    if(first == null) return null;
    Node secondMin;

    return null; // TODO
}

This is the psuedo code I have so far but I need help turning it into code. Do I have initialize a min and a secondMin node?

EDIT: This is what I have so far

public Key secondMinKey () {
  if(first == null) return null;
    Node secondMin;
    for (Node x = first.next.next; x != null; x = x.next) {
        if (need to update min) update min and second min
        else if (need to update second min) update second min
    }
    return second min;
}

Upvotes: 1

Views: 379

Answers (1)

Debosmit Ray
Debosmit Ray

Reputation: 5413

To find the second smallest element in a linked list, I can think of a decently slick solution. The algorithm kinda goes like this.

Have 2 "pointers". Initialize both to the maximum possible value of Key.

firstPtr = secondPtr = Key.MAX_VALUE;

Parse through the linked list with the following conditions

  1. If current Node.Key is smaller than firstPtr, update both firstPtr and secondPtr to the current Node.Key.
  2. Else if the current Node.Key is smaller than secondPtr then update secondPtr.

Let me know if you are having issues coding this up.

Upvotes: 1

Related Questions