LinkedList Interview Question | LinkedList Practice Question.

 1. Find the nth node from the end of the linked list.

public int findNthNode(MyLinkedList list, int index) {
  MyNode temp = list.head;
  int count = 0;
  int data = -1;
  if (list.head == null) {
    System.out.println("Item Not Found ! MyLinkedList is Empty");
    return -1;
  } else {
    while (temp.next != null) {
      count++;
      if (count == index) {
        data = temp.data;
      }
      temp = temp.next;
    }
  }
  return data;
}

2. Find loop in a linked list. If it has loop, find the start node of the
loop.

public void findLoop(MyLinkedList list) {
  MyNode temp = list.head;
  MyNode previousNode = temp;
  Map<MyNode, Integer> map = new HashMap();
  while (temp != null && temp.next != null) {
    if (map.containsKey(temp)) {
      System.out.println("found Loop in LinkedList   " + previousNode.data);
      return;
    }
    map.put(temp, 1);
    previousNode = temp;
    temp = temp.next;
  }
  System.out.println("no Loop Found");
}
3. Insert a node in sorted linked list.
public MyLinkedList insertNodeInSortedList(MyLinkedList list, int data) {
  MyNode currentNode = list.head;
  MyNode node = new MyNode(data);
  if (list.head == null || list.head.data > node.data) {
    node.next = list.head;
    list.head = node;
  } else {
    while (currentNode.next != null && currentNode.next.data < node.data) {
      currentNode = currentNode.next;
    }
    MyNode temp = currentNode.next;
    currentNode.next = node;
    node.next = temp;
  }
  return list;

}
4. Reverse a singly linked list.
public void revLinkedList(MyNode node) {
  if (node == null || node.next == null) {
    return;
  }

  MyNode preNode = null;
  MyNode currNode = node;
  MyNode nextNode;

  while (currNode != null) {
    nextNode = currNode.next;
    currNode.next = preNode;
    //update
    preNode = currNode;
    currNode = nextNode;
  }
  System.out.println();
  while (preNode != null) {
    System.out.print(preNode.data + " -> ");
    preNode = preNode.next;
  }
}
5. Find the middle of linked list.
public void findMiddle(MyNode head) {
  int size = 0;
  if (head == null) {
    System.out.println("List id empty");
    return;
  } else if (head.next == null) {
    System.out.println("List size is 1");

  }
  //find the size of list...
  MyNode temp = head;
  while (temp != null) {
    size++;
    temp = temp.next;
  }
  temp = head;
  int middle = size / 2;
  while (temp != null && middle > 0) {
    middle--;
    temp = temp.next;

  }
  System.out.println(temp.data);
}

//Second Method to solve above problem
public void findMiddle1(MyNode head) {
  MyNode fast = head, slow = head;
  while (fast != null) {

    fast = fast.next;
    if (fast != null) {
      fast = fast.next;
      slow = slow.next;
    }
  }
  System.out.println(slow.data);

}
6. Display a linked list from the end.
public void printFromLast(MyNode head){
  if(head==null){
    return;
  }
  printFromLast(head.next);
  System.out.print(head.data+" ");
}
7. Check whether given linked list length is even or odd?
public void findSizeEvenOdd(MyNode node) {
  if (node == null) {
    System.out.println("List size is 0");
    return;
  }
  MyNode temp = node;
  int count = 0;
  while (temp != null) {
    count++;
    temp = temp.next;
  }
  if (count % 2 == 0) {
    System.out.println("List size is Even");
  } else {
    System.out.println("List size is Odd");
  }
}
8. Given two sorted linked list, merge them into
the third list in sorted order.

9. Reverse the linked list in pairs.
10. Given a linked list consists of data, next pointer and also a random
pointer which points to a random node of the list. Give an algorithm for
cloning the list.