Questions On Linked List
Problem 1: Remove duplicates from an unsorted Linked List.
The simplest solution of this problem is- run two loops for the items – select each item and search through the list.
public class RemoveDuplicatesFromUnsortedList {
public static void deleteDuplicates(Node start) {
Node current = start;
while (current != null) {
Node next = current.next;
Node previous = current;
while (next != null) {
if (current.value == next.value) {
previous.next = next.next;
} else {
previous = next;
}
next = next.next;
}
current = current.next;
}
}
public static void main(String[] args) {
LinkedList linkList = new LinkedList();
linkList.insertAtEnd(5);
linkList.insertAtEnd(20);
linkList.insertAtEnd(5);
linkList.insertAtEnd(5);
linkList.insertAtEnd(40);
linkList.insertAtEnd(5);
linkList.insertAtEnd(40);
System.out.println("List: ");
linkList.displayList();
deleteDuplicates(linkList.first);
System.out.println("After removal of duplicates: ");
linkList.displayList();
}
}
Output
---------
List:
{5} {20} {5} {5} {40} {5} {40}
After removal of duplicates:
{5} {20} {40}
This solution is not very time efficient. It will take O(n2) time. We can do it in O(n) time using java.util.Set. Set doesn’t allow duplicates and we know that Set add method return false if Set already have the added element.Add list element to Set, if it return false while adding change the previous pointer next to the current next.
import java.util.HashSet;
import java.util.Set;
public class RemoveDuplicatesFromUnsortedList {
public static void deleteDuplicates(Node start) {
Set<Integer> set = new HashSet<>();
Node current = start;
Node previous = start;
while (current != null) {
if (!set.add(current.value)) {
previous.next = current.next;
} else {
previous = current;
}
current = current.next;
}
}
public static void main(String[] args) {
LinkedList linkList = new LinkedList();
linkList.insertAtEnd(5);
linkList.insertAtEnd(20);
linkList.insertAtEnd(5);
linkList.insertAtEnd(5);
linkList.insertAtEnd(40);
linkList.insertAtEnd(5);
linkList.insertAtEnd(40);
System.out.println("List: ");
linkList.displayList();
deleteDuplicates1(linkList.first);
System.out.println("After removal of duplicates: ");
linkList.displayList();
}
}
Output
-------
List:
{5} {20} {5} {5} {40} {5} {40}
After removal of duplicates:
{5} {20} {40}
Problem 2: Write code to create a sorted list.
To create a sorted list, you will have to take care while inserting the element. The new element should be inserted at right position such that all its predecessor are smaller and all its successor are greater.
public class SortedLinkedList {
private Node first;
public SortedLinkedList() {
first = null;
}
public void insert(int value) {
Node node = new Node(value);
if (first == null) {
first = node;
} else {
if (first.value > value) {
node.next = first;
first = node;
} else {
Node current = first;
Node previous = first;
while (current.next != null) {
if (current.value > value) {
previous.next = node;
node.next = current;
break;
}
previous = current;
current = current.next;
}
if (current.next == null){ // reached to last of the list
current.next = node;
}
}
}
}
public void displayList() {
Node current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
SortedLinkedList linkList = new SortedLinkedList();
linkList.insert(10);
linkList.insert(20);
linkList.insert(5);
linkList.insert(1);
linkList.insert(40);
linkList.insert(60);
linkList.insert(100);
linkList.displayList();
}
}
Output
--------
[1]-> [5]-> [10]-> [20]-> [40]-> [60]-> [100]->
Problem 3: Display a Singly Linked List in reverse order.
You can easily display a list in reverse using Stack.
public class DisplayReverse {
public static void displayReverse(Node first) {
Stack<Integer> stack = new Stack<>();
Node current = first;
while (current != null) {
stack.push(current.info);
current = current.next;
}
while (stack.size() > 0) {
System.out.print(stack.pop() + " ");
}
System.out.println();
}
public static void main(String[] args) {
LinkList linkedList = new LinkList();
linkedList.insertFirst(5);
linkedList.insertFirst(10);
linkedList.insertFirst(15);
linkedList.insertFirst(20);
System.out.println("List-");
linkedList.displayList();
System.out.println("Printed in reverse order-");
displayReverse(linkedList.first);
}
}
Output
--------
List-
[20]->[15]->[10]->[5]->
Printed in reverse order-
5 10 15 20
Problem 4: Implement an algorithm to find the Kth to last element of a Singly Linked List.
There are recursive solution also for this problem but I will find the iterative one easy. In iterative solution we maintain two pointers let say P1 and P2. Point P1 to the first element and move P2 to the Kth node. Now start moving P1 and P2 to the next node until P2 reaches to the end. Please note that P1 is running K node behind P2 therefore when P2 will reach to the end P1 will be at Kth node from the last.
public class KthToLastNode {
public static Node kthToLastNode(Node first,int k) {
assert first != null : "list should not be empty";
assert k > 0 : "position should be greater than 0";
Node current = first;
Node nodeBehind = first;
for (int i = 0; i < k; i++) {
if (current == null) {
return null;
}
current = current.next;
}
while (current != null) {
nodeBehind = nodeBehind.next;
current = current.next;
}
return nodeBehind;
}
public static void main(String[] args) {
LinkList linkList = new LinkList();
linkList.insertLast(6);
linkList.insertLast(5);
linkList.insertLast(10);
linkList.insertLast(4);
linkList.insertLast(12);
linkList.insertLast(3);
linkList.insertLast(2);
linkList.displayList();
System.out.println(kthToLastNode(linkList.first,3).info);
}
}
Output
--------
[6]->[5]->[10]->[4]->[12]->[3]->[2]->
The 3rd from last is: 12
The 5th from last is: 10
Problem 5: Write a program to reverse a Singly Linked List.
public class ReverseList {
public static Node reverseList(Node start) {
assert start != null : "Empty list!";
Node prev = null;
Node curr = start;
while (curr != null) {
Node next = curr.next; // don't loss the 3rd pointer
curr.next = prev; // point second to first(next to previous)
prev = curr; // move previous to the
curr = next; // move curr to preserved next pointer
}
start = prev;
return start;
}
public static void main(String[] args) {
LinkList linkedList = new LinkList();
linkedList.insertLast(5);
linkedList.insertLast(10);
linkedList.insertLast(15);
linkedList.insertLast(20);
linkedList.displayList();
linkedList.first = reverseList(linkedList.first);
linkedList.displayList();
}
}
Output
-------
[5]->[10]->[15]->[20]->
[20]->[15]->[10]->[5]->
Problem 6: Write a program to find whether two list interest or not?
import java.util.HashSet;
import java.util.Set;
public class LinkListIntersection {
public static boolean isListsIntersects(Node start1, Node start2) {
assert start1 != null && start2 != null : "One or both of the list is empty";
Set<Integer> set = new HashSet<Integer>();
Node current1 = start1;
while (current1 != null) {
set.add(current1.info);
current1 = current1.next;
}
Node current2 = start2;
while (current2 != null) {
boolean isAdded = set.add(current2.info);
if (!isAdded) {
return true;
}
current2 = current2.next;
}
return false;
}
public static void main(String[] args) {
LinkList linkedList1 = new LinkList();
linkedList1.insertFirst(5);
linkedList1.insertFirst(10);
linkedList1.insertFirst(15);
linkedList1.insertFirst(20);
linkedList1.displayList();
LinkList linkedList2 = new LinkList();
linkedList2.insertFirst(10);
linkedList2.insertFirst(45);
linkedList2.insertFirst(25);
linkedList2.insertFirst(60);
linkedList2.displayList();
System.out.println("Is Intersect:: " + isListsIntersects(linkedList1.first, linkedList2.first));
}
}
Output
-------
[20]->[15]->[10]->[5]->
[60]->[25]->[45]->[10]->
Is Intersect:: true
Problem 7: Copy a linked list with next and arbitrary pointer.
There is a Doubly Linked List given with one pointer of each node pointing to the next node as in a singly linked list. The second pointer is an arbitrary pointer and can point to any node in the list and not just the previous node. Write a program in O(n) time to copy this list.
To create a copy of the List:
-
- First create a copy of all nodes with next pointer as it is in original list.
- Point next pointer of each node of the original list to the corresponding node of the copy list.
- Point the arbitrary pointer of each node of the copy list to the corresponding node in the original list.
-
- Construct the copy list as below.
copyListNode->arbitPtr = copyListNode->arbitPtr->arbitPtr->next;
copyListNode = copyListNode->next;
Java Implementation
First create a Node class with next and arbitrary pointer.
public class Node {
int value;
Node nextPtr;
Node arbtPtr;
public Node(int value) {
this.value = value;
}
public void displayNode() {
System.out.print("Value: " + value);
if (nextPtr != null)
System.out.print(" nextPtr: " + nextPtr.value);
else{
System.out.print(" nextPtr: " + nextPtr);
}
if (arbtPtr != null)
System.out.print(" arbitPtr: " + arbtPtr.value);
System.out.println();
}
}
public class CopyListWithArbitaryPointer {
public static Node copyList(Node start){
Node head = null;
Node currCopyPtr = null;
Node currNode = start;
while(currNode != null){
Node node = new Node(currNode.value);
if(head == null){
head = node;
currCopyPtr = head;
}else{
currCopyPtr.nextPtr = node;
currCopyPtr = currCopyPtr.nextPtr;
}
currNode = currNode.nextPtr;
}
currNode = start;
currCopyPtr = head;
Node nextPtr = start;
while(currNode != null){
nextPtr = currNode.nextPtr;
currNode.nextPtr = currCopyPtr;
currCopyPtr.arbtPtr = currNode;
currCopyPtr = currCopyPtr.nextPtr;
currNode = nextPtr;
}
currCopyPtr = head;
while(currCopyPtr != null){
currCopyPtr.arbtPtr = currCopyPtr.arbtPtr.arbtPtr;
currCopyPtr = currCopyPtr.nextPtr;
}
return head;
}
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node8 = new Node(8);
node1.nextPtr = node2;
node2.nextPtr = node3;
node3.nextPtr = node4;
node4.nextPtr = node5;
node5.nextPtr = node6;
node6.nextPtr = node7;
node7.nextPtr = node8;
node8.nextPtr = null;
node1.arbtPtr = node8;
node2.arbtPtr = node7;
node3.arbtPtr = node5;
node4.arbtPtr = node2;
node5.arbtPtr = node6;
node6.arbtPtr = node3;
node7.arbtPtr = node4;
node8.arbtPtr = node1;
Node currNode = node1;
System.out.println("-----List With Arbitrary Pointer-----");
while(currNode != null){
currNode.displayNode();
currNode = currNode.nextPtr;
}
System.out.println("-----AFTER COPY-----");
Node head = copyList(node1);
while(head != null){
head.displayNode();
head = head.nextPtr;
}
}
}
Output
--------
-----List With Arbitrary Pointer-----
Value: 1 nextPtr: 2 arbitPtr: 8
Value: 2 nextPtr: 3 arbitPtr: 7
Value: 3 nextPtr: 4 arbitPtr: 5
Value: 4 nextPtr: 5 arbitPtr: 2
Value: 5 nextPtr: 6 arbitPtr: 6
Value: 6 nextPtr: 7 arbitPtr: 3
Value: 7 nextPtr: 8 arbitPtr: 4
Value: 8 nextPtr: null arbitPtr: 1
-----AFTER COPY-----
Value: 1 nextPtr: 2 arbitPtr: 8
Value: 2 nextPtr: 3 arbitPtr: 7
Value: 3 nextPtr: 4 arbitPtr: 5
Value: 4 nextPtr: 5 arbitPtr: 2
Value: 5 nextPtr: 6 arbitPtr: 6
Value: 6 nextPtr: 7 arbitPtr: 3
Value: 7 nextPtr: 8 arbitPtr: 4
Value: 8 nextPtr: null arbitPtr: 1
References:
- Introduction To Algorithm – CLRS.
- Data Structures and Algorithms in Java – Adam Drozdek
- Data Structure & Algorithms In Java – Robert Lafore
- Cracking The Coding Interview- Gayle Laakmann McDowell
- Programming Interviews Exposed- John Mongan, Eric Giguère, Noah Kindler.
- Coding Interviews- Harry He