Linked List

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

by

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:

Singly Linked List To BST
Singly Linked List To BST

Approach:

Read more

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

by

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:

Read more

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

by

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

Read more

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

by

We have similar post – Two numbers represented by a linked list, Number Stored in FORWARD order

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:

Read more

Reverse a Linked List – Part 2

by

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:

Recursion:

Read more

Swap Every Kth Node in a LinkedList

by

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:

Read more

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

by

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

Read more

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

by

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:

Recursive Approach:

Read more

Remove Duplicates from an Unsorted Linked list

by

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.

Read more

Find Intersection Point in Two Linked List

by

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

An intersection point means the 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
Find Intersection Point in Two Linked List

Approach:

Read more

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

by

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
Loop in a Linked List
Loop in a Linked List

Approach:

Read more

Reverse a Linked List

by

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:

Iterative:

Read more

Merge or Combine Two Sorted Linked Lists

by

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:

Without Recursion:


Read more
 













Singly Linked List Implementation
 

 by  













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;
	}
}



Node
Node


Read more