Find second largest value in a single linked list with O(n) traversal

Algorithm:

 step1: Initialize the variable max to first value of the linked list and secondMax to second value;
step 2: Assign node to temp Node to traverse the linked list.
step 3:For each traversal , compare max value to each node.value and if node.value is greater than max, assign max value to secondMax and node value to max. If max is greater than node.value and secondMax is less than node.value,  assign only node.value to secondMax .
step 4: Print the secondMax.



Coding

ListNode.Java

public class ListNode {
Node node = null;
public ListNode() {

}

public ListNode(int val) {
node = new Node(val);
node.next = null;
}

// adding node to single linked list
public void addNode(int val) {
Node last = node;
while(last.next!=null) {
last = last.next;    
}
last.next = new Node(val);
last.next.next = null;
}


// traversing Node
public void traverse(){
Node first = node;
while(first != null) {
System.out.print(first.val+",");
first = first.next;
}
System.out.println();
}

// Method to find second largest value
public void secondLargestNode() {
int max = node.val;
int secondMax;
if(node.next!=null) {
secondMax = node.next.val;
Node temp = node;
while(temp!=null) {
if(max<temp.val) {
secondMax = max;
max = temp.val;
}
if(max>temp.val && secondMax < temp.val) {
secondMax = temp.val;
}
temp = temp.next;
}
System.out.println(" second largest node value is :"+secondMax);
} else {
System.out.println(" Doesnt have second largest node");
}


}
}

Node.java

public class Node {

public int val;

public Node next;

public Node(int val) {

this.val = val;

}

}

SecondLargestNode.java

public class SecondLargestNode {

public static void main(String[] args) {

ListNode list1 =  new ListNode(1);

list1.addNode(4);

list1.addNode(7);

list1.addNode(13);

list1.addNode(19);

list1.traverse();

list1.secondLargestNode();

}

}

Click to Read more Data structure questions and answer