Linked List | Algorithms

Given a Sorted Singly Linked List Array, Convert it into a Balanced Binary search Tree.

May 30, 2020November 18, 2014 by Sumit Jain

Given a Sorted Array, Convert it into its Balanced Binary search TreeObjective: You have been given a sorted singly List, you need to convert it into balanced binary search tree.

Why balanced binary tree is important:

You can also create the first node as root and insert all other nodes to the right of the tree because List is in increasing order but this constructed tree won’t be a balanced tree, it will be the skewed tree and to perform operations on this tree will be O(n), not O(logn).

Input: An sorted Singly Linked List

Output: Balanced Binary Tree

Example:

Approach:

Convert a Sorted Doubly Linked List to Balanced BST.

August 31, 2019November 18, 2014 by Sumit Jain

Objective: Given a sorted doubly linked list, convert it into Balanced binary search tree

Input: A Doubly Linked List

Example:

Approach:

In a Binary Tree, Create Linked Lists of all the nodes at each depth.

August 31, 2019September 22, 2014 by Sumit Jain

Objective: Given a Binary tree create Linked Lists of all the nodes at each depth , say if the tree has height k then create k linked lists.

NOTE : This problem is very similar “Print binary tree, each level in one line“

Input: A binary tree

Output: K linked lists if the height of tree is k. Each linked list will have all the nodes of each level.

Example:

Add two numbers represented by a linked list, Numbers are Stored in FORWARD order

May 21, 2020September 16, 2014 by Sumit Jain

This post is the extension of – Two numbers represented by a linked list, Number Stored in REVERSE order

Objective: Two numbers represented by a linked listwhere each node contains single digit. The digits are stored in Forward order, means head is pointing to the last digit of the number.

Input: Two numbers represented by Linked Lists

Output: Addition of two numbers represented by a Linked List.

Example:

First Number : 1007
Second Number : 93
Addition : 1100

Add two numbers represented by a linked list, Numbers are Stored in REVERSE order

May 21, 2020September 16, 2014 by Sumit Jain

Objective: Two numbers represented by a linked list where each node contains single digit. The digits are stored in REVERSE order, means head is pointing to the first digit of the number.

Input: Two numbers represented by Linked Lists

Output: Addition of two numbers represented by a Linked List.

Example:

First Number in REVERSE order: 5957
Second Number in REVERSE order : 59
Addition in REVERSE order : 0967
Actual Result in FORWARD ORDER : 9670

Approach:

Reverse a Linked List – Part 2

May 21, 2020September 14, 2014 by Sumit Jain

This post is the extension of our earlier post Reverse a linked list. Here We have provided the better recursive solution in which we start reversing the list from the end.

Objective: Reverse the given linked list.

Input: A Linked List

Output: Reversed Linked List

Example:

Original List :->10->8->6->4->2
Reversed List :->2->4->6->8->10

Approach:

Swap Every Kth Node in a LinkedList

May 21, 2020September 14, 2014 by Sumit Jain

Objective: Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched.

Input: A linked list, A number k.

Example:

Input : ->1->2->3->4->5->6->7->8->9->10 , K = 4
Output: ->4->2->3->1->8->6->7->5->9->10

Approach:

Delete a Node in the Middle of a linked list, Given only access to that Node

May 21, 2020September 12, 2014 by Sumit Jain

Objective: Write a program to Delete a Node in the Middle of a linked list, Given only access to that Node

Example:

Original List : ->1->2->8->3->7->0->4
After Deleting the mid node (say 7) : ->1->2->8->3->0->4

Input: A Linked List and access to the node which needs to be deleted

Output: Linked list with deleted node

Approach:

Approach is tricky and simple
Copy the value of next node to the node which you want to delete
Delete the next node

Find the n’th Node from the end of a given Linked List

May 21, 2020September 12, 2014 by Sumit Jain

Objective: Given a linked list and integer ‘n’, write an algorithm to find the nth node from the end in the Linked List.

Example:

Original List : ->1->2->8->3->7->0->4
Output : 3rd Element from the end is : 7

Input: An unsorted linked list and integer k

Output: The kth to Last Element of a Singly Linked List

Approach:

Remove Duplicates from an Unsorted Linked list

May 21, 2020September 11, 2014 by Sumit Jain

Objective: Write a program to remove the duplicates from an unsorted linked list

Example:

Input Linked List : 1->2->2->4->3->3->2
Output : 1->2->4->3

Input: An unsorted linked list

Output: Linked list with no duplicates.

Approach:

Create a Hash Map
Take two pointers, prevNode and CurrNode.
PrevNode will point to the head of the linked list and currNode will point to the head.next.

Find Intersection Point in Two Linked List

August 14, 2020September 6, 2014 by Sumit Jain

Objective: Given Two linked list, check whether both list intersect each other, if yes then find the starting node of the intersection.

Intersection point means end of one linked list is linked with some node in another linked list and it forms a Y shape.

Input: Two Linked List

Output: Intersection Node or point

Example:

Find Intersection Point in Two Linked List

Approach:

Find the Loop in a Linked list, find its length and Break the Loop

May 21, 2020September 5, 2014 by Sumit Jain

Objective: In a given linked list, check whether it contains the loop in it, if yes then find the Loop length and break the loop.

Loop in a linked list means the last node does not point to the null, instead it points to some node in the list.

Input: A Linked List

Output: Linked list contains loop or not, if yes its length and linked list after breaking the loop.

Example: 

Input : ->10->20->30->40->50->60->30->40->50->60->30->40->50->60->30

here you can see that 30->40->50->60 are repeating ,that means it has a loop

Approach:

Reverse a Linked List

May 21, 2020August 28, 2014 by Sumit Jain

Objective: Reverse the given linked list.

Input: A Linked List

Output: Reversed Linked List

Example:

Input : ->30->25->20->15->10->5

Reversed : ->5->10->15->20->25->30

NOTE : Click Reverse a Linked List – Part 2 to see the another implementation of this problem.

Approach:

Merge or Combine Two Sorted Linked Lists

August 14, 2020August 12, 2014 by Sumit Jain

Objective: Given two sorted linked lists, objective is to merge both the lists in sorted order.

Input: Two sorted linked list List a, List b.

Example: 

List a : ->2->6->18

Listb: ->1->3->17->19

Merged List: ->1->2->3->6->17->18->19

Approach:

Singly Linked List Implementation

May 21, 2020August 12, 2014 by Sumit Jain

Linked List- As the name suggests it’s a list which is linked.

Linked List consist of Nodes

Nodes are nothing but objects of a class and each node has data and a link to the next node.

class Node {
	public int data;
	public Node next;

	public Node(int data) {
		this.data = data;
		this.next = null;
	}
}