LinkedList based Programs : Good to practice before an interview

Program 1: Find the middle element of a singly linked list in one pass?

public class LinkedList{

private Node head;

private static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

public void addToTheLast(Node node) {

if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}


public void printList() {
Node temp = head;
while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}

// This function will find middle element in linkedlist
public Node findMiddleNode(Node head)
{
Node slowPointer, fastPointer;
slowPointer = fastPointer = head;

while(fastPointer !=null) {
fastPointer = fastPointer.next;
if(fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next;
}
}

return slowPointer;

}

public static void main(String[] args) {
LinkedList list = new LinkedList();
// Creating a linked list
Node head=new Node(5);
list.addToTheLast(head);
list.addToTheLast(new Node(6));
list.addToTheLast(new Node(7));
list.addToTheLast(new Node(1));
list.addToTheLast(new Node(2));

list.printList();
// finding middle element
Node middle= list.findMiddleNode(head);
System.out.println("Middle node will be: "+ middle.value);

}
}

output :

5 6 7 1 2
Middle node is: 7


Program 2: Reverse a linked list in java ?

public class LinkedList{

private Node head;

private static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

public void addToTheLast(Node node) {

if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}


public void printList(Node head) {
Node temp = head;
while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}

// Reverse linkedlist using this function
public static Node reverseLinkedList(Node currentNode)
{
// For first node, previousNode will be null
Node previousNode=null;
Node nextNode;
while(currentNode!=null)
{
nextNode=currentNode.next;
// reversing the link
currentNode.next=previousNode;
// moving currentNode and previousNode by 1 node
previousNode=currentNode;
currentNode=nextNode;
}
return previousNode;
}

public static void main(String[] args) {
LinkedList list = new LinkedList();
// Creating a linked list
Node head=new Node(5);
list.addToTheLast(head);
list.addToTheLast(new Node(6));
list.addToTheLast(new Node(7));
list.addToTheLast(new Node(1));
list.addToTheLast(new Node(2));

list.printList(head);
//Reversing LinkedList
Node reverseHead=reverseLinkedList(head);
System.out.println("After reversing");
list.printList(reverseHead);

}

}


Output :

5 6 7 1 2
After reversing
2 1 7 6 5


Program 3: How to detect loop in a linked list in java ? or linked list contains loop in java ?

public class LinkedList{

private Node head;

private static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

public void addToTheLast(Node node) {

if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}


public void printList() {
Node temp = head;
while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}

public boolean ifLoopExists() {
Node fastPtr = head;
Node slowPtr = head;
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
if (slowPtr == fastPtr)
return true;

}
return false;
}

public static void main(String[] args) {
LinkedList list = new LinkedList();
// Creating a linked list

list.addToTheLast(new Node(5));
list.addToTheLast(new Node(6));
list.addToTheLast(new Node(7));
list.addToTheLast(new Node(1));
list.addToTheLast(new Node(2));


list.printList();

// Test if loop existed or not
System.out.println("Loop existed-->" + list.ifLoopExists());

}
}

output:

5 6 7 1 2
Loop existed-->false


Program 4: Find start node of loop in linked list in java ?

public class LinkedList{

private Node head;

private static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

public void addToTheLast(Node node) {

if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}


public void printList() {
Node temp = head;
while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}

public Node  findStartNodeOfTheLoop() {
Node fastPtr = head;
Node slowPtr = head;
boolean loopExists=false;
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
if (slowPtr == fastPtr)
{
loopExists=true;
break;
}

}
if(loopExists)
{
slowPtr=head;

while(slowPtr!=fastPtr)
{
slowPtr=slowPtr.next;
fastPtr=fastPtr.next;
}


}
else
{
System.out.println("Loop does not exists");
slowPtr=null;
}
return slowPtr;
}


public static void main(String[] args) {
LinkedList list = new LinkedList();
// Creating a linked list
Node loopNode=new Node(7);
list.addToTheLast(new Node(5));
list.addToTheLast(new Node(6));
list.addToTheLast(loopNode);
list.addToTheLast(new Node(1));
list.addToTheLast(new Node(2));

list.printList();
list.addToTheLast(loopNode); 

Node startNode=list.findStartNodeOfTheLoop();
if(startNode!=null)
System.out.println("start Node of loop is "+ startNode.value);
}
}

output:

5 6 7 1 2
start Node of loop is 7



Program 5:  Find nth element from end of linked list using java ?

public class LinkedList{

private Node head;

private static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

public void addToTheLast(Node node) {

if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}


public void printList() {
Node temp = head;
while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}


public Node nthFromLastNode(Node head,int n)
{
Node firstPtr=head;
Node secondPtr=head;

for (int i = 0; i < n; i++) {
firstPtr=firstPtr.next;

}

while(firstPtr!=null)
{
firstPtr=firstPtr.next;
secondPtr=secondPtr.next;
}

return secondPtr;
}

public static void main(String[] args) {
LinkedList list = new LinkedList();
// Creating a linked list
Node head=new Node(5);
list.addToTheLast(head);
list.addToTheLast(new Node(6));
list.addToTheLast(new Node(7));
list.addToTheLast(new Node(1));
list.addToTheLast(new Node(2));

list.printList();
// Finding 3rd node from end
Node nthNodeFromLast= list.nthFromLastNode(head,3);
System.out.println("3th node from end is : "+ nthNodeFromLast.value);

}
}

output:

5 6 7 1 2
3th node from end is : 7


Program 6: How to check if linked list is palindrome in java ?


public class LinkedListPalindromeCheck{

private Node head;

private static class Node {
private int value;
private Node next;

Node(int value) {
this.value = value;

}
}

public void addToTheLast(Node node) {

if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}


public void printList() {
Node temp = head;
while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}

// This function will find middle element in linkedlist
public static Node findMiddleNode(Node head)
{
// step 1
Node slowPointer, fastPointer;
slowPointer = fastPointer = head;

while(fastPointer !=null) {
fastPointer = fastPointer.next;
if(fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next;
}
}

return slowPointer;
}

// Function to check if linked list is palindrome or not
public static boolean checkPalindrome (Node head)
{
// Find middle node using slow and fast pointer
Node middleNode=findMiddleNode(head);
// we got head of second part
Node secondHead=middleNode.next;
// It is end of first part of linked list
middleNode.next=null;
// get reversed linked list for second part
Node reverseSecondHead=reverseLinkedList(secondHead);

while(head!=null && reverseSecondHead!=null)
{
if(head.value==reverseSecondHead.value)
{
head=head.next;
reverseSecondHead=reverseSecondHead.next;
continue;
}
else
{
return false;
}
}

return true;


}

public static Node reverseLinkedList(Node currentNode)
{
// For first node, previousNode will be null
Node previousNode=null;
Node nextNode;
while(currentNode!=null)
{
nextNode=currentNode.next;
// reversing the link
currentNode.next=previousNode;
// moving currentNode and previousNode by 1 node
previousNode=currentNode;
currentNode=nextNode;
}
return previousNode;
}


public static void main(String[] args) {
LinkedListPalindromeCheck list = new LinkedListPalindromeCheck();
// Creating a linked list
Node head=new Node(1);
list.addToTheLast(head);
list.addToTheLast(new Node(2));
list.addToTheLast(new Node(1));
list.addToTheLast(new Node(2));
list.addToTheLast(new Node(1));

list.printList();

System.out.println("Linked list palidrome: "+checkPalindrome(head));
}
}


output :

1 2 1 2 1
Linked list palidrome: true


Program 7: Find the sum of two linked list using Stack


import java.util.Stack;

public class AddNumbersLinkedList
{
    private class ListNode
    {
        int value;
        ListNode next;

        ListNode(int value)
        {
            this.value = value;
        }
    }
   
    ListNode head;
    ListNode tail;
   
    // appends node at the end of the list
    private void appendNode(int value)
    {
        if (head == null)
        {
            head = new ListNode(value);
            tail = head;
            return;
        }
       
        ListNode n = new ListNode(value);
        tail.next = n;
        tail = n;
    }

    // creates and returns a new list with node values taken from the stack 's'
    private ListNode createLinkedList(Stack<Integer> s)
    {
        // if the head is pointing to some existing list, make it null
        // let the clients handle and store the reference to head
        if (head != null)
        {
            head = null;
        }
       
        while (!s.isEmpty())
        {
            appendNode(s.pop());
        }
        return head;
    }
   
    // creates and returns a new list with node values taken from number[] array
    public ListNode createLinkedList(int[] number)
    {
        // if the head is pointing to some existing list, make it null
        // let the clients handle and store the reference to head
        if (head != null)
        {
            head = null;
        }
       
        for (int i = 0; i < number.length; i++)
        {
            appendNode(number[i]);
        }
        return head;
    }
   
    public void printList(ListNode head)
    {
        ListNode temp = head;
       
        while (temp != null)
        {
            System.out.print(temp.value + "->");
            temp = temp.next;
        }
        System.out.print("null");
    }
   
   
    public ListNode addLists(ListNode node1, ListNode node2)
    {
        if (node1 == null)
        {
            return node2;
        }
        if (node2 == null)
        {
            return node1;
        }
       
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();
        Stack<Integer> s3 = new Stack<Integer>();
       
        // push list1 into the first stack
        ListNode temp = node1;
        while (temp != null)
        {
            s1.push(temp.value);
            temp = temp.next;
        }
       
        // push list2 into the second stack
        temp = node2;
        while (temp != null)
        {
            s2.push(temp.value);
            temp = temp.next;
        }

        int sum = 0, carry = 0, value1, value2;
       
        // keep adding the popped digits to the sum until one of the stacks becomes empty
        // sum itself is stored in a stack
        while ((!s1.empty()) && (!s2.empty()))
        {
            value1 = s1.pop();
            value2 = s2.pop();
           
            sum   = (value1 + value2 + carry) % 10;
            carry = (value1 + value2 + carry) / 10;
           
            s3.push(sum);
        }
       
        // if stack1 still has some digits left, add those digits to the sum
        while (!s1.isEmpty())
        {
            value1 = s1.pop();
           
            sum   = (value1 + carry) % 10;
            carry = (value1 + carry) / 10;
           
            s3.push(sum);
        }
       
        // if stack2 still has some digits left, add those digits to the sum
        while (!s2.isEmpty())
        {
            value2 = s2.pop();
           
            sum   = (value2 + carry) % 10;
            carry = (value2 + carry) / 10;
           
            s3.push(sum);
        }
       
        // after adding digits from both the stack, if the remaining carry is greater than 0
        // add that carry to the sum
        if (carry > 0)
        {
            s3.push(carry);
        }
       
        // finally, from the resultant stack, which stores the sum create a new linked list
        // return this newly created linked list
        return createLinkedList(s3);
    }
   
   
    public static void main(String[] args)
    {
        AddNumbersLinkedList solution = new AddNumbersLinkedList();

        int[] firstNumber  = {9,9,9,7,1}; // number: 99971
        int[] secondNumber = {9,9,8}; // number: 998
       
        // 9->9->9->7->1->null
        ListNode head1 = solution.createLinkedList(firstNumber);
       
        // 9->9->8->null
        ListNode head2 = solution.createLinkedList(secondNumber);
       
        ListNode result = solution.addLists(head1, head2);
       
        System.out.print("Resultant sum represented as a linked list is: \n");
        solution.printList(result);
    }
}


Program 8: Find the length of a singly linked list?


public class LinkedListMain {
 // Find length of linked list using recursion
public int lengthOfLinkedList()
{
  Node temp=head;
  int count = 0;
  while(temp!=null)
  {
   temp=temp.next;
   count++; 
  }
  return count;
} 
  public static void main(String args[])
  {
   SinglyLinkedList myLinkedlist = new SinglyLinkedList();
   myLinkedlist.insertFirst(5);
   myLinkedlist.insertFirst(6);
   myLinkedlist.insertFirst(7);
   myLinkedlist.insertFirst(1);
   myLinkedlist.insertLast(2);
   myLinkedlist.printLinkedList();
   // Linked list will be
   // 2 -> 1 ->  7 -> 6 -> 5
   System.out.println("Length of Linked List using iteration: "+myLinkedlist.lengthOfLinkedList());
   System.out.println("Length of Linked List Using recursion: "+myLinkedlist.lengthOfLinkedListRec(myLinkedlist.getHead()));
 }
}

output:

1
2
3
4
5
6
7
8
9
10

Printing LinkedList (head --> last)
{ 1 }
{ 7 }
{ 6 }
{ 5 }
{ 2 }

Length of Linked List using iteration: 5
Length of Linked List Using recursion: 5

class Node {
 public int data;
 public Node next;

 public void displayNodeData() {
  System.out.println("{ " + data + " } ");
 }
}

public class SinglyLinkedList {
 private Node head;

 public boolean isEmpty() {
  return (head == null);
 }

 // used to insert a node at the start of linked list
 public void insertFirst(int data) {
  Node newNode = new Node();
  newNode.data = data;
  newNode.next = head;
  head = newNode;
 }

// Find length of linked list using iterative method
public int lengthOfLinkedList()
{
   Node temp=head;
   int count = 0;
   while(temp!=null)
   {
  temp=temp.next;
  count++; 
   }
    return count;
}
// Find length of linked list using recursion
public int lengthOfLinkedListRec(Node head)
 {
   Node temp=head;
   if(temp==null)
   {
      return 0;
    }
   else
   {
      return 1+ lengthOfLinkedListRec(temp.next);
    }
}
 // used to delete node from start of linked list
 public Node deleteFirst() {
  Node temp = head;
  head = head.next;
  return temp;
 }

 // used to delete node from start of linked list
 public Node deleteFirst(Node node) {
  Node temp = head;
  head = head.next;
  return temp;
 }

 // Use to delete node after particular node
 public void deleteAfter(Node after) {
  Node temp = head;
  while (temp.next != null && temp.data != after.data) {
   temp = temp.next;
  }
  if (temp.next != null)
   temp.next = temp.next.next;
 }

 // used to insert a node at the start of linked list
 public void insertLast(int data) {
  Node current = head;
  while (current.next != null) {
   current = current.next; // we'll loop until current.next is null
  }
  Node newNode = new Node();
  newNode.data = data;
  current.next = newNode;
 }

 // For printing Linked List
 public void printLinkedList() {
  System.out.println("Printing LinkedList (head --> last) ");
  Node current = head;
  while (current != null) {
   current.displayNodeData();
   current = current.next;
  }
  System.out.println();
 }
}

Program 9: Remove duplicate nodes in an unsorted linked list?

import java.util.HashMap;
import java.util.Map;

public class RemoveDuplicateLinkedList {
public static void main(String[] args) {

Node head = new Node("1");
head.next = new Node("2");
head.next.next = new Node("2");
head.next.next.next = new Node("4");
head.next.next.next.next = new Node("5");
head.next.next.next.next.next = new Node("4");
head.next.next.next.next.next.next = new Node("3");
       
System.out.println("Original List : ");
        display(head);
       
        System.out.println("\nUpdated List: ");
        Node update = deDup(head);
        display(update);
}

private static Node deDup(Node head) {

if(head == null || head.next == null) {
return head;
}

Node prevNode = head;
Node currNode = head.next;
Node temp = null;

Map<String, Integer> map = new HashMap<>();

map.put(prevNode.data, 1);

while(currNode != null) {

if(map.containsKey(currNode.data)) {
temp = currNode;
prevNode.next = currNode.next;
currNode = currNode.next;
temp = null;
}else {
map.put(currNode.data, 1);
prevNode = currNode;
currNode = currNode.next;
}

}
return head;
}

private static void display(Node head){
        Node n=head;
        while(n!=null){
            System.out.print("->" + n.data);
            n=n.next;
        }
}

}

public class Node {

    Node next;
    String data;
   
    public Node(String data) {
super();
this.data = data;
     }
}