Introduction TO Linked Lists

A linked list is a linear data structure consisting of nodes where each node contains data and a
pointer to the next node in the list. There are two kinds of linked lists:

 Singly linked list

 Doubly link

Singly Linked List

A singly linked list can only be traversed in one direction, meaning, from the first node (head)
towards the last node. The last node points to NULL, indicating the end of the list.

Pros
 Insertion and deletion at head is more efficient compared to the corresponding operations in
an array.
 Changes are localized when inserting and deleting somewhere in the middle of the linked
list. In the case of an array, all subsequent elements need to be moved around. Of course, if
you first have to search for the position to insert or delete in a linked list, then it still
takes O(n) in the worst case.

Cons
 As each node also contains a pointer, it has a memory overhead.
 We cannot access a node through indexing directly, rather we have to traverse from the start
to access an element at a given position n.
 Reverse traversing is not possible with a singly linked list.

Doubly Linked List

Each node in a doubly linked list contains a pointer to the next node as well as pointer to the
previous node. This allows the list to be traversed in both directions: forward and backward.

Doubly linked lists have all the advantages of singly-linked lists while providing some additional pros
and cons.

Pros
 Insert and delete at the head as well as tail are O(1) operations
 The list can be traversed forward as well as backward

Cons
 Have greater space overhead than singly-linked lists
Singly vs. Doubly linked list table
Deletion at the tail is one of the operations that distinguishes a doubly-linked list from a singly-linked
list. The following table shows a side by side comparison of key operations on both.

Operation Singly Linked List Doubly Linked Li

Insert at head O(1) O(1)

Delete at head O(1) O(1)

Insert at tail O(n) O(1)

Delete at tail O(n) O(1)

In terms of space, if there are n nodes in a linked list, d is the (average) number of bytes of data in
each node and p is the number of bytes consumed by a pointer, then a singly linked
list consumes n*(d+p) bytes, whereas a doubly linked list consumes n*(d+2p) bytes.

Insertion in a Singly Linked List (insert

at End)
Introduction
Now, we are going to explain the second part (Insertion at End) and look at its examples, along with
one coding challenge for the sake of practice. So let’s see how elements are inserted at the end of a
linked list. In this type of insertion, we add an element at the end of the list.

Problem Statement
In the code snippet provided below, you will complete the void insertAtEnd(T data) method. This will
take a generic type T value called data and insert that value at the end of the list. This code would
be the part of the SinglyLinkedList class that we created in the previous lesson, therefore, any
private members of that class can be accessed inside the function as well. After writing the code, run
it and see how many tests you passed.

Method Prototype
void insertAtEnd(T data)

Output
The return type of the method is void. The object on which it is called will be modified only.

Sample Input
linkedlist = 0->1->2 data = 3

Sample Output
linkedlist = 0->1->2->3

Soution
If you grasped the logic behind insertion at the head of a linked list, this shouldn’t be much of a
challenge. If the list is empty, the situation is exactly like insertion at the head. Otherwise, we can
use a loop to reach the tail of the list and set our new node as the nextNode of the last node.

Code
public class SinglyLinkedList<T> {
//Node inner class for SLL
public class Node {
public T data;
public Node nextNode;

public Node headNode; //head node of the linked list

public int size; //size of the linked list

//Constructor - initializes headNode and size

public SinglyLinkedList() {
headNode = null;
size = 0;
}

//Helper Function that checks if List is empty or not

public boolean isEmpty() {
if (headNode == null) return true;
return false;
}

//Inserts new data at the start of the linked list

public void insertAtHead(T data) {
//Creating a new node and assigning it the new data value
Node newNode = new Node();
newNode.data = data;
//Linking head to the newNode's nextNode
newNode.nextNode = headNode;
headNode = newNode;
size++;
}

// Helper Function to printList

public void printList() {
 if (isEmpty()) {
System.out.println("List is Empty!");
return;
}

Node temp = headNode;

System.out.print("List : ");
while (temp.nextNode != null) {
System.out.print(temp.data.toString() + " -> ");
temp = temp.nextNode;
}
System.out.println(temp.data.toString() + " -> null");
}

//Inserts new data at the end of the linked list

public void insertAtEnd(T data) {
//if the list is empty then call insertATHead()
if (isEmpty()) {
insertAtHead(data);
return;
}
//Creating a new Node with value data
Node newNode = new Node();
newNode.data = data;
newNode.nextNode = null;

Node last = headNode;

//iterate to the last element
while (last.nextNode != null) {
last = last.nextNode;
}
//make newNode the next element of the last node
last.nextNode = newNode;
size++;
}
}

Time Complexity
This algorithm traverses the entire linked list, and hence, works in O(n) time.

Search in Singly Linked List

Introduction
Now, we will take a look at the second most important operation, i.e. searching for an element in a
linked list. This exercise of finding a value in a Singly Linked List is relatively more straightforward
than the other three operations of insertion.

The steps to search for a node in a Singly Linked List are as follows:

 Start from the headNode.

 Traverse the list till you either find a node with the given value, or you reach the end showing
that the node being searched doesn’t exist.
Problem Statement
If you know how to insert an element in a list, then searching for an item will not be that difficult for
you. Now, based on the steps mentioned above, we have designed a simple coding exercise for
your practice. There is a solution placed in the solution section for your help, but try to solve it on
your own first.

Method Prototype
boolean searchNode(T data)

Output
It returns true or false to show if a certain value does or does not exists in the list.

Sample Input
linkedlist = 5->90->10->4 and value = 4

Sample Output
true

Soution
In this function, we traverse through the list, checking whether the currentNode’s data matches the
searched value data. If the currentNode’s data matches the searched value data, we will
return True else we will return False.

Code
public class SinglyLinkedList<T> {
//Node inner class for SLL
public class Node {
public T data;
public Node nextNode;

//head node of the linked list

public Node headNode;
public int size;

//constructor
public SinglyLinkedList() {
headNode = null;
size = 0;
}

public boolean isEmpty() {

 if (headNode == null) return true;
return false;
}

//Inserts new data at the start of the linked list

public void insertAtHead(T data) {
//Creating a new node and assigning it the new data value
Node newNode = new Node();
newNode.data = data;
//Linking head to the newNode's nextNode
newNode.nextNode = headNode;
headNode = newNode;
size++;
}

//Inserts new data at the end of the linked list

public void insertAtEnd(T data) {
//if the list is empty then call insertATHead()
if (isEmpty()) {
insertAtHead(data);
return;
}
//Creating a new Node with value data
Node newNode = new Node();
newNode.data = data;
newNode.nextNode = null;

Node last = headNode;

//iterate to the last element
while (last.nextNode != null) {
last = last.nextNode;
}
//make newNode the next element of the last node
last.nextNode = newNode;
size++;
}

//inserts data after the given prev data node

public void insertAfter(T data, T previous) {

//Creating a new Node with value data

Node newNode = new Node();
newNode.data = data;
//Start from head node
Node currentNode = this.headNode;
//traverse the list until node having data equal to previous is found
while (currentNode != null && currentNode.data != previous) {
currentNode = currentNode.nextNode;
}
//if such a node was found
//then point our newNode to currentNode's nextElement
if (currentNode != null) {
newNode.nextNode = currentNode.nextNode;
currentNode.nextNode = newNode;
size++;
}
}

public void printList() {

if (isEmpty()) {
 System.out.println("List is Empty!");
return;
}

Node temp = headNode;

System.out.print("List : ");

while (temp.nextNode != null) {

System.out.print(temp.data.toString() + " -> ");
temp = temp.nextNode;
}

System.out.println(temp.data.toString() + " -> null");

}

//Searches a value in the given list.

public boolean searchNode(T data) {
//Start from first element
Node currentNode = this.headNode;

//Traverse the list till you reach end

while (currentNode != null) {
if (currentNode.data.equals(data))
return true; //value found

currentNode = currentNode.nextNode;
}
return false; //value not found
}
}

Time Complexity
The time complexity for this algorithm is O(n) because we have to traverse through the list

Deletion in Singly Linked List(Delete by

Value)
Introduction
This operation deletes the required node, e.g., n, from any position in a Singly Linked List. This
deletion follows the following steps:

 It takes in the value that needs to be deleted from the list.

 It traverses the list searching for that value.
 Once the node (n) with the required value is found, it connects n's previous node to the
nextNode of n.
 It then removes n from the list.

Problem Statement
In the code snippet given below, you have to implement the void deleteByValue(T data) method.
In this method, we will pass a particular value that we want to delete from the list. The node
containing this value could be anywhere on the list. It is also possible that such a node may not exist
at all. Therefore, we would have to traverse the whole list until we find the value which needs to be
deleted. If the value doesn’t exist, we simply return control to the calling function.
Note: This function removes only the first occurrence of the value from the list.

Method Prototype
void deleteByValue(T data)

Output
A linked list with the element removed.

Sample Input
linkedlist = 3->2->1->0, data = 1

Sample Output
linkedlist = 3->2->0

Soution
While traversing through the linked list, there are three cases we can come across:

 List is empty
 One element in the list
 More than one element in the list
If the list is empty, then we have nothing to do; just return the control to calling function. For a single
element in the list, we’ll call deleteAtHead(), and this will delete the value at the head.
If there is more than one element in the list, then we simply start traversing from the headNode and
keep on checking until that node found and delete it.

Code
public class SinglyLinkedList<T> {
//Node inner class for SLL
public class Node {
public T data;
public Node nextNode;

//head node of the linked list

public Node headNode;
public int size;
//constructor
public SinglyLinkedList() {
headNode = null;
size = 0;
}

public boolean isEmpty() {

if (headNode == null) return true;

return false;
}

//Inserts new data at the start of the linked list

public void insertAtHead(T data) {
//Creating a new node and assigning it the new data value
Node newNode = new Node();
newNode.data = data;
//Linking head to the newNode's nextNode
newNode.nextNode = headNode;
headNode = newNode;
size++;
}

//Inserts new data at the end of the linked list

public void insertAtEnd(T data) {
//if the list is empty then call insertATHead()
if (isEmpty()) {
insertAtHead(data);
return;
}
//Creating a new Node with value data
Node newNode = new Node();
newNode.data = data;
newNode.nextNode = null;

Node last = headNode;

//iterate to the last element
while (last.nextNode != null) {
last = last.nextNode;
}
//make newNode the next element of the last node
last.nextNode = newNode;
size++;
}

//inserts data after the given prev data node

public void insertAfter(T data, T previous) {

//Creating a new Node with value data

Node newNode = new Node();
newNode.data = data;
//Start from head node
Node currentNode = this.headNode;
//traverse the list until node having data equal to previous is found
while (currentNode != null && currentNode.data != previous) {
currentNode = currentNode.nextNode;
}
//if such a node was found
//then point our newNode to currentNode's nextElement
if (currentNode != null) {
newNode.nextNode = currentNode.nextNode;
 currentNode.nextNode = newNode;
size++;
}
}

public void printList() {

if (isEmpty()) {
System.out.println("List is Empty!");
return;
}

Node temp = headNode;

System.out.print("List : ");

while (temp.nextNode != null) {

System.out.print(temp.data.toString() + " -> ");
temp = temp.nextNode;
}

System.out.println(temp.data.toString() + " -> null");

}

//Searches a value in the given list.

public boolean searchNode(T data) {
//Start from first element
Node currentNode = this.headNode;

//Traverse the list till you reach end

while (currentNode != null) {
if (currentNode.data.equals(data))
return true; //value found

currentNode = currentNode.nextNode;
}
return false; //value not found
}

//Deletes data from the head of list

public void deleteAtHead() {
//if list is empty then simply return
if (isEmpty())
return;
//make the nextNode of the headNode equal to new headNode
headNode = headNode.nextNode;
size--;
}

//Deletes data given from the linked list

public void deleteByValue(T data) {
//if empty then simply return
if (isEmpty())
return;

//Start from head node

Node currentNode = this.headNode;
Node prevNode = null; //previous node starts from null

if(currentNode.data.equals(data)) {
//data is at head so delete from head
deleteAtHead();
return;
 }
//traverse the list searching for the data to delete
while (currentNode != null) {
//node to delete is found
if (data.equals(currentNode.data)){
prevNode.nextNode = currentNode.nextNode;
size--;
return;
}
prevNode = currentNode;
currentNode = currentNode.nextNode;
}
}
}
deleteByValue(): It takes a value as a parameter. Additionally, it searches for a node in the Singly
Linked List that has the given data value while keeping track of current and previous nodes. If not
found, it means no such value exists in the list. If found, it performs a series of steps to delete this
value. However, before jumping to those steps, look at some of the terminologies that we used in the
function:
 currentNode – node we are currently standing at
 prevNode – element that comes before currentNode
 nextNode – pointer to the next node of currentNode
Executing the single line of code,

prevNode.nextNode = currentNode.nextNode

links the prevNode to the nextNode. The current node’s link will be destroyed from the list, and the
garbage collector will take care of the deletion automatically.

Time Complexity
In the worst case, you would have to traverse until the end of the list. This means the time
complexity will be O(n).

Linked Lists vs. Arrays

Let's put the two data structures against each other to find out which is more efficient.

Memory Allocation
The main difference between a linked list and an array is the way they are allocated memory. Arrays
instantiate a whole block of memory, e.g., array[1000] gets space to store 1000 elements at the start
even if it doesn’t contain any element yet. On the other hand, a linked list only instantiates the
portion of memory it uses.

Insertion and Deletion

For lists and arrays, many differences can be observed in the way elements are inserted and
deleted. In a linked list, insertion and deletion at head happen in a constant amount of time (O(1)),
while arrays take O(n) time to insert or delete a value because you have to shift the array elements
left or right after that operation.
Searching
In an array, it takes constant time to access an index. In a linked list, you have to iterate the list from
the start until you find the node with the correct value.

The table given below will summarize the performance difference between linked lists and arrays.

Operation Linked List A

Access O(n) O(1)

Insert (at head) O(1) O(n)

Delete (at head) O(1) O(n)

Insert (at tail) O(n) O(n)

Delete (at tail) O(n) O(n)

As you can see, there is a trade-off between the facilities provided by both structures. You will
understand more about the working of linked lists in the lessons that follow.

Find the Length of a Linked List

Problem Statement
In this problem, you have to implement the method int length(), which will count the number of
nodes in a linked list. An illustration is also provided for your understanding.

Method Prototype
int length()

Output
The length of the given linked list.

Sample Input
linkedlist = 0->1->2-3->4

Sample Output
length = 5

Solution
class CheckLength {
 public static void main( String args[] ) {
SinglyLinkedList<String> list = new SinglyLinkedList<String>();
list.insertAtEnd("This");
list.insertAtEnd("list");
list.insertAtEnd("is");
list.insertAtEnd("Generic");
list.printList();
System.out.println("Length : " + list.length());
}
}

Explanation
The logic behind it is very similar to that of the search function. The trick is to iterate through the list
and keep count of how many nodes you’ve visited. This count is held in a variable that is returned
when the end of the list is reached.

Time Complexity
Since this is a linear algorithm, the time complexity will be O(n).

Reverse a Linked List

Problem Statement
In this problem, you have to implement the public static void reverse(SinglyLinkedList list)
method, which will take a linked list as input and reverse its content. An illustration is also provided
for your help to see how the linked list will look after passing it to your function.

Method Prototype
public static void reverse(SinglyLinkedList list)

Output
A Singly linked list with all its content stored in reverse order.

Sample Input
linkedlist = 10->9->4->4-6

Sample Output
linkedlist = 6->4->4->9->10

Solution
public static void reverse(SinglyLinkedList list){
SinglyLinkedList.Node previous = null; //To keep track of the previous element, will be used in
swapping links
SinglyLinkedList.Node current = list.headNode; //firstElement
SinglyLinkedList.Node next = null;

//While Traversing the list, swap links

while (current != null) {
next = current.nextNode;
current.nextNode = previous;
previous = current;
current = next;
}
//Linking Head Node with the new First Element
list.headNode = previous;
}

Explanation
The brain of this solution lies in the loop, which iterates through the list. For any current node, its
link with the previous node is reverse and the next stores next node in the list:
 Store the current node’s nextNode in next
 Set current node’s nextNode to previous (reversal)
 Make the current node the new previous so that it can be used for the next iteration
 Use next to move on to the next node
In the end, we simply point the head to the last node in our loop.

Time Complexity
The algorithm runs in O(n) since the list is traversed once.

Detect Loop in a Linked List

Problem Statement
In this problem, you have to implement the public static boolean detectLoop(SinglyLinkedList
list) method, which will take a Singly linked list as input and find if there is a loop present in the list.
A loop in a linked list occurs if any node contains a reference to any previous node, then a loop will
be formed. An illustration is also provided for your understanding.

Method Prototype
public static boolean detectLoop(SinglyLinkedList list)

Output
It returns true if a loop exists in the linked list; otherwise, false.
Sample Input
linkedlist = 7->14->21->7

Sample Output
true

Solution

public static boolean detectLoop(SinglyLinkedList list) {

SinglyLinkedList.Node slow = list.headNode;
SinglyLinkedList.Node fast = list.headNode;

while(slow != null && fast != null && fast.nextNode != null)

{
slow = slow.nextNode; //the slow pointer will jump 1 step
fast = fast.nextNode.nextNode; //the fast pointer will jump 2 steps
// when the pointers become equal then there must be a loop
if(slow == fast){
return true;
}
}
return false;
}

Explanation
This is the most optimized method to find out the loop in the LinkedList. We start traversing the
LinkedList using two pointers called slow and fast. Move slow by one (line # 9) and fast by two (line
# 10). If these pointers meet at the same node, then there is a loop. If these pointers do not meet,
then LinkedList doesn’t have a loop.

Time Complexity
The algorithm runs in Constant with O(n) with the Auxiliary Space complexity of O(1).

Find the Middle Node of a Linked List

Problem Statement
In this problem, you have to implement the public static Object findMiddle(SinglyLinkedList
list) method, which will take a linked list as an input and return the value at the middle node of the
list. An illustration is also provided for your understanding.

Method Prototype
public static Object findMiddle(SinglyLinkedList list)
Output
The value at the middle node in a linked list.

Sample Input
linkedlist = 7->14->10->21

Sample Output
mid = 14

Solution
public static Object findMiddle(SinglyLinkedList list) {
//if list is empty, then return null
if (list.isEmpty())
return null;

//both nodes start from the head

SinglyLinkedList.Node mid = list.headNode;
SinglyLinkedList.Node current = list.headNode;

while(mid != null && current != null && current.nextNode != null)

{
//current jumps 2 nodes on each iteration
current = current.nextNode.nextNode;
//if current is not null (end of list is not reached)
if(current != null){
//then mid jumps 1 node
//mid is always halfway behind current
mid = mid.nextNode;
}
}
return mid.data;
}

Explanation
We are using two pointers, which will work simultaneously. Think of it this way:

 The current pointer moves two steps at a time till the end of the list
 The mid pointer moves one step at a time
 When the current pointer reaches the end, the mid pointer will be at the middle

Time Complexity
We are traversing the linked list at twice the speed, so it is certainly faster. However, the bottleneck
complexity is still O(n).
Remove Duplicates from a Linked List
Problem Statement
In this problem, you have to implement public static void removeDuplicates(SinglyLinkedList
list) method. This method will take a Singly linked list as input and remove all the elements that
appear more than once in the list. An illustration is also provided for your understanding.

Method Prototype
public static void removeDuplicates(SinglyLinkedList list)

Output
The linked list with all the duplicates removed.

Sample Input
linkedlist = 7->14->21->14->22->null

Sample Output
linkedlist = 7->14->21->22->null

Solution
public static void removeDuplicates(SinglyLinkedList list) {
SinglyLinkedList.Node current = list.headNode; // will be used for outer loop
SinglyLinkedList.Node compare = null; // will be used for inner loop

while (current != null && current.nextNode != null) {

compare = current;
while (compare.nextNode != null) {
if (current.data.equals(compare.nextNode.data)) { //check if duplicate
compare.nextNode = compare.nextNode.nextNode;
} else {
compare = compare.nextNode;
}
}
current = current.nextNode;
}
}

Explanation
This solution is simply a brute force solution. In this solution, we traverse the linked list using two
loops. The pointer current keeps track of the outer loop, and the pointer compare is used for the
inner loop. When both of these pointers point to the same value, then that node is deleted. This is
not the most efficient approach to solve this problem. It can also be solved using a Hash Table.

Time Complexity
This algorithm has two nested loops. Hence, the time complexity is O(n^2).
Note: The solution provided above is not the optimal solution for this problem. A more efficient
approach is to use hashing instead.

Return the Nth node from End

Problem Statement
In this problem, you have to implement Object nthElementFromEnd(SinglyLinkedList list, int
n) method, which will take a linked list as an input and returns the nth element of the list from the
end. To solve this, you will have to come up with a formula by comparing multiple outputs and inputs
and identifying a common pattern. An illustration is also provided for your understanding.

Method Prototype
public static Object nthElementFromEnd(SinglyLinkedList list, int n)

Output
It will return nth node from the end of the linked list.

Sample Input
linkedlist = 22->18->60->78->47->39->99 and n=3

Sample Output
47

Solution
public static Object nthElementFromEnd(SinglyLinkedList list, int n) {
int size = list.getSize();
n = size - n + 1; //we can use the size variable to calculate distance from start
if (size == 0 || n > size) {
return null; //returns null if list is empty or n is greater than size
}
SinglyLinkedList.Node current = list.getHeadNode();
int count = 1;
//traverse until count is not equal to n
while (current != null) {
if (count == n)
return current.data;
 count++;
current = current.nextNode;
}
return null;
}

Explanation
In the above solution, we first use the getter function list.getSize() to access the length of the list.
Then we find the node which is at x position from the start.

Time Complexity
In the worst-case time complexity of this algorithm is O(n). Because we might have to access the 1st
element from the end.

Implementation of Linked List

Linked list implementation will be covered in this lesson. We'll use this implementation in the whole
chapter. Before moving on to the challenges of the linked list, let’s look at the implementation
of LinkedListNode and LinkedList classes first. These classes are prepended in all the coming
challenges of the chapter.

Implementation of LinkedListNode Class

class LinkedListNode {
public int key;
public int data;
public LinkedListNode next;
public LinkedListNode arbitraryPointer;

public LinkedListNode(int data) {

this.data = data;
this.next = null;
}

public LinkedListNode(int key, int data) {

this.key = key;
this.data = data;
this.next = null;
}

public LinkedListNode(int data, LinkedListNode next) {

this.data = data;
this.next = next;
}

public LinkedListNode(int data, LinkedListNode next, LinkedListNode

arbitraryPointer) {
this.data = data;
this.next = next;
 this.arbitraryPointer = arbitraryPointer;
}
}

Implementation of LinkedList Class

import java.util.*;

class LinkedList {

public static LinkedListNode insertAtHead(LinkedListNode head, int data) {

LinkedListNode newNode = new LinkedListNode(data);
newNode.next = head;
return newNode;
}

public static LinkedListNode insertAtTail(LinkedListNode head, int data) {

LinkedListNode newNode = new LinkedListNode(data);
if (head == null) {
return newNode;
}
LinkedListNode temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
return head;
}

public static LinkedListNode createLinkedList(ArrayList<Integer> lst) {

LinkedListNode head = null;
LinkedListNode tail = null;
for (Integer x : lst) {
LinkedListNode newNode = new LinkedListNode(x);
if (head == null) {
head = newNode;
} else {
tail.next = newNode;
}
tail = newNode;
}
return head;
}

public static LinkedListNode createLinkedList(int[] arr) {

LinkedListNode head = null;
LinkedListNode tail = null;
for (int i = 0; i < arr.length; ++i) {
LinkedListNode newNode = new LinkedListNode(arr[i]);
if (head == null) {
head = newNode;
} else {
tail.next = newNode;
}
tail = newNode;
}
return head;
}
 public static LinkedListNode createRandomList(int length) {
LinkedListNode listHead = null;
Random generator = new Random();
for(int i = 0; i < length; ++i) {
listHead = insertAtHead(listHead, generator.nextInt(100));
}
return listHead;
}

public static void display(LinkedListNode head) {

LinkedListNode temp = head;
while (temp != null) {
System.out.printf("%d", temp.data);
temp = temp.next;
if (temp != null) {
System.out.printf(", ");
}
}
System.out.println();
}
}

class Pair<X, Y> {

public X first;
public Y second;
public Pair(X first, Y second) {
this.first = first;
this.second = second;
}
}

Intersection Point of Two Lists

Given the head nodes of two linked lists that may or may not intersect, find out if they intersect and
return the point of intersection. Return null otherwise.

Description
Given the head nodes of two linked lists that may or may not intersect, find out if they do in fact
intersect and return the point of intersection. Return null otherwise

Hints
 Find the length of both linked lists.
 The linked lists have to physically intersect. This means that their addresses need to be the
same. If two nodes have the same data but their addresses are not the same, the lists won’t
intersect and the function should return NULL.

Solution
The first solution that comes to mind is one with quadratic time complexity, i.e., for each node in the
first linked list, a linear scan must be done in the second linked list. If any node from the first linked
list is found in the second linked list (comparing addresses of nodes, not their data), that is the
intersection point. However, if none of the nodes from the first list is found in the second list, that
means there is no intersection point. Although this works, it is not efficient. A more efficient solution
would be to store the nodes of the first linked list in a HashSet and then go through the second
linked list nodes to check whether any of the nodes exist in the HashSet. This approach has a linear
runtime complexity and linear space complexity. We can use a much better, i.e., O(m + n), linear
time complexity algorithm that doesn’t require extra memory. To simplify our problem, let’s say both
the linked lists are of the same size. In this case, you can start from the heads of both lists and
compare their addresses. If these addresses match, it means it is an intersection point. If they don’t
match, move both pointers forward one step and compare their addresses. Repeat this process until
an intersection point is found, or both of the lists are exhausted. How do we solve this problem if the
lists are not of the same length? We can extend the linear time solution with one extra scan on the
linked lists to find their lengths. Below is the complete algorithm:
Find lengths of both linked lists: L1 and L2 Calculate the difference in length of both linked lists: d = |
L1 - L2| Move head pointer of longer list 'd' steps forward Now traverse both lists, comparing nodes
until we find a match or reach the end of lists

Code
class Intersect{
public static LinkedListNode intersect(LinkedListNode head1, LinkedListNode head2) {

LinkedListNode list1node = null;

int list1length = get_length(head1);
LinkedListNode list2node = null;
int list2length = get_length(head2);

int length_difference = 0;
if(list1length >= list2length) {
length_difference = list1length - list2length;
list1node = head1;
list2node = head2;
} else {
length_difference = list2length - list1length;
list1node = head2;
list2node = head1;
}

while(length_difference > 0) {
list1node = list1node.next;
length_difference--;
}

while(list1node != null) {
if(list1node == list2node) {
return list1node;
}

list1node = list1node.next;
list2node = list2node.next;
}
return null;
}

private static int get_length(

LinkedListNode head) {
int list_length = 0;
 while(head != null) {
head = head.next;
list_length++;
}
return list_length;
}
public static void main(String[] args) {
int [] a1 = {13,4};
int [] a2 = {29, 23, 82, 11};
LinkedListNode list_head_1 = LinkedList.createLinkedList(a1);
LinkedListNode list_head_2 = LinkedList.createLinkedList(a2);
LinkedListNode node1 = new LinkedListNode(12);
LinkedListNode node2 = new LinkedListNode(27);

LinkedList.insertAtTail(list_head_1, node1);
LinkedList.insertAtTail(list_head_1, node2);

LinkedList.insertAtTail(list_head_2, node1);

System.out.print("List 1: ");
LinkedList.display(list_head_1);
System.out.print("List 2: ");
LinkedList.display(list_head_2);

LinkedListNode intersect_node = intersect(list_head_1, list_head_2);

System.out.println(String.format("Intersect at %d", intersect_node.data));
}
}

Runtime complexity
The runtime complexity of this solution is linear, O(m + n) Where m is the length of the first linked list
and n is the length of the second linked list.

Memory complexity
The memory complexity of this solution is constant, O(1).

Reverse Alternate K Nodes in a Singly

Linked List
Given a singly linked list and an integer 'k', reverse every 'k' element. If k <= 1, then the input list is
unchanged. If k >= n (n is the length of linked list), then reverse the whole linked list.

Description
Given a singly linked list and an integer ‘k’, reverse every ‘k’ element. If k <= 1, then the input list is
unchanged. If k >= n (n is the length of the linked list), then reverse the whole linked list.

Hints
  Reverse the first k element, then move to the next k element.

Solution
Algorithmically, it is a simple problem, but writing code for this is a bit trickier as it involves keeping
track of a few pointers. Logically, we break down the list to sub-lists each of size ‘k’. We’ll use the
below pointers:

 reversed: it points to the head of the output list.

 current_head: head of the sub-list of size ‘k’ currently being worked upon.
 current_tail: tail of the sub-list of size ‘k’ currently being worked upon.
 prev_tail: tail of the already processed linked list (where sub-lists of size ‘k’ have been
reversed).
We’ll work upon one sub-list of size ‘k’ at a time. Once that sub-list is reversed, we have its head and
tail in current_head and current_tail respectively. If it was the first sub-list of size ‘k’, its head
(i.e., current_head) is the head (i.e., reversed) of the output linked list. We’ll
point reversed to current_head of the first sub-list. If it is the 2nd or higher sub-list, we’ll connect the
tail of the previous sub-list to head of the current sub-list, i.e., update next pointer of the tail of the
previous sub-list with the head pointer of current sub-list to join the two sub-lists.

Code
class ReverseK{
static LinkedListNode reverseKNodes(LinkedListNode head, int k) {

// if k is 0 or 1, then list is not changed

if (k <= 1 || head == null) {
return head;
}

LinkedListNode reversed = null;

LinkedListNode prevTail = null;

while (head != null && k > 0) {

LinkedListNode currentHead = null;
LinkedListNode currentTail = head;

int n = k;
while (head != null && n > 0) {
LinkedListNode temp = head.next;
head.next = currentHead;
currentHead = head;

head = temp;
n--;
}

if (reversed == null) {
reversed = currentHead;
}

if (prevTail != null) {
prevTail.next = currentHead;
}
prevTail = currentTail;
}
 return reversed;
}

public static void main(String[] args) {

int[] v1 = new int[]{1, 2, 3, 4, 5, 6, 7};
LinkedListNode listHead = LinkedList.createLinkedList(v1);
System.out.print("Original list: ");
LinkedList.display(listHead);

listHead = reverseKNodes(listHead, 4);

System.out.print("List reversed by 4: ");
LinkedList.display(listHead);
}
}

Runtime complexity
The runtime complexity of this solution is linear, O(n).

Memory complexity
The memory complexity of this solution is constant, O(1).

Merge K Sorted Lists

Problem Statement
Given an array of ‘K’ sorted LinkedLists, merge them into one sorted list.

Example 1:
Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4] Output: [1, 2, 3, 3, 4, 6, 6, 7, 8]

Example 2:
Input: L1=[5, 8, 9], L2=[1, 7] Output: [1, 5, 7, 8, 9]

Solution
A brute force solution could be to add all elements of the given ‘K’ lists to one list and sort it. If there
are a total of ‘N’ elements in all the input lists, then the brute force solution will have a time
complexity of O(NlogN)* as we will need to sort the merged list. Can we do better than this? How
can we utilize the fact that the input lists are individually sorted? If we have to find the smallest
element of all the input lists, we have to compare only the smallest (i.e. the first) element of all the
lists. Once we have the smallest element, we can put it in the merged list. Following a similar
pattern, we can then find the next smallest element of all the lists to add it to the merged list.
The best data structure that comes to mind to find the smallest number among a set of ‘K’ numbers
is a Heap. Let’s see how can we use a heap to find a better algorithm.
 We can insert the first element of each array in a Min Heap.
 After this, we can take out the smallest (top) element from the heap and add it to the merged
list.
 After removing the smallest element from the heap, we can insert the next element of the
same list into the heap.
 We can repeat steps 2 and 3 to populate the merged list in sorted order.

Code
import java.util.*;

class ListNode {
int value;
ListNode next;

ListNode(int value) {
this.value = value;
}
}

class MergeKSortedLists {

public static ListNode merge(ListNode[] lists) {

PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>((n1, n2) -> n1.value
- n2.value);

// put the root of each list in the min heap

for (ListNode root : lists)
if (root != null)
minHeap.add(root);

// take the smallest (top) element form the min-heap and add it to the result;
// if the top element has a next element add it to the heap
ListNode resultHead = null, resultTail = null;
while (!minHeap.isEmpty()) {
ListNode node = minHeap.poll();
if (resultHead == null) {
resultHead = resultTail = node;
} else {
resultTail.next = node;
resultTail = resultTail.next;
}
if (node.next != null)
minHeap.add(node.next);
}

return resultHead;
}

public static void main(String[] args) {

ListNode l1 = new ListNode(2);
l1.next = new ListNode(6);
l1.next.next = new ListNode(8);

ListNode l2 = new ListNode(3);

 l2.next = new ListNode(6);
l2.next.next = new ListNode(7);

ListNode l3 = new ListNode(1);

l3.next = new ListNode(3);
l3.next.next = new ListNode(4);

ListNode result = MergeKSortedLists.merge(new ListNode[] { l1, l2, l3 });

System.out.print("Here are the elements form the merged list: ");
while (result != null) {
System.out.print(result.value + " ");
result = result.next;
}
}
}

Time complexity
Since we’ll be going through all the elements of all arrays and will be removing/adding one element
to the heap in each step, the time complexity of the above algorithm will be O(N*logK), where ‘N’ is
the total number of elements in all the ‘K’ input arrays.

Space complexity
The space complexity will be O(K) because, at any time, our min-heap will be storing one number
from all the ‘K’ input arrays