The Coding Shala

Home >> Data Structures >> Linked List Introduction and its Implementation  In this post, we will learn what is linked list data structure and will implement a singly linked list in Java. Linked List Data Structure A linked list is a linear data structure. The linked list is a chain of Nodes that are connected using pointers. One Node contains the data/element and a pointer called next that points to the next node. Unlike arrays, linked list elements are not stored in a contiguous location. There are different types of the linked lists like a singly linked list, doubly linked list, and circular linked list. Here we will cover a singly linked list. The following are main terms used in a linked list: head: front node of a linked list next: pointer to the next node node: contains data/value and the next pointer We can create a linked list of different data types like integer, string, etc. Advantages and Disadvantages of linked lists The following are some advan...

Home >> Interview Prep >> Find the middle element in a linked list  In this post, we will learn how to find the middle element in a linked list and will implement its solution in Java. Find a middle element in a linked list Problem Given a singly linked list of N nodes. The task is to find the middle of the linked list. Example 1: Input: LinkedList: 1->2->3->4->5 Output: 3  Explanation:  Middle of linked list is 3. Example 2:  Input: LinkedList: 2->4->6->7->5->1 Output: 7  Explanation:  Middle of linked list is 7. Find a middle element in a linked list Java Solution Approach 1 You can find the total length of the linked list then traverse again from starting and return the middle element. A better approach is to take two pointers one is a slow pointer, move by one step, and one fast pointer, move by two steps. At the time the fast pointer reaches the end slow is at the middle node. Java Program:  /* No...

Home >> Interview Prep >> Merge k Sorted Lists  In this post, we will learn how to solve the Merge k Sorted Lists problem and will implement its solution in Java. Merge k Sorted Lists Problem You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Example 1: Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [   1->4->5,   1->3->4,   2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6 Merge k Sorted Lists Solution Approach 1 We can use an additional array to store all the elements from lists and then will sort this array. From the sorted array, we can make the linked list again. Time Complexity: O(n logn) Space Complexity: O(N) Java Program:  /** * Definition for singly-linked list. * public class ListNode { * int v...

Home >> Data Structures >> Find the Length of a Linked List using Recursion  In this post, we will learn how to find the length of a linked list using recursion in Java. How to Find the Length of a Linked List using Recursion You have given a singly linked list, write a Java program to count the number of elements or length of the linked list using recursion. Example 1: LinkedList: 1->2->3->4->5 Output: 5 Example 2: LinkedList: 2->4->6->7->5->1->0 Output: 7 Approach 1 If the current node is null then it will be our break condition of recursion. Java Program:  /* class Node{ int data; Node next; Node(int a){ data = a; next = null; } }*/ class Solution { public static int getCount ( Node head ) { return findLength ( head ); } public static int findLength ( Node curr ) { if ( curr == null ) { return 0 ; } ...

Home >> Data Structures >> Find the Length of a Linked List  In this post, we will learn how to find the length of a given linked list in Java. How to Find the Length of a Linked List You have given a singly linked list, write a Java program to count the number of elements or length of the linked list. Example 1: LinkedList: 1->2->3->4->5 Output: 5 Example 2: LinkedList: 2->4->6->7->5->1->0 Output: 7 Approach 1 Traverse the linked list until you reached the null node. Java Program:  /* class Node{ int data; Node next; Node(int a){ data = a; next = null; } }*/ class Solution { public static int getCount ( Node head ) { int count = 0 ; Node curr = head ; while ( curr != null ) { count ++; curr = curr . next ; } return count ; } } Other Posts You May Like Design Linked List...

Home >> Interview Prep >> Remove Duplicates from Sorted Linked List  In this post, we will learn how to Remove Duplicates from Sorted Linked List in Java. Remove Duplicates from Sorted Linked List Problem Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well. Example 1: Input: head = [1,1,2] Output: [1,2] Example 2: Input: head = [1,1,2,3,3] Output: [1,2,3] Remove Duplicates from Sorted Linked List Java Solution Approach 1 Iterative method. Time Complexity: O(n) Space Complexity: O(1) Java Program:  /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode deleteDuplicates ( ListNode head ) { if ( head =...

Home >> Interview Questions >> sort a linked list using insertion sort  In this post, we will learn how to sort a linked list using insertion sort and will implement a Java solution. Sort a linked list using insertion sort in Java Sort a linked list using insertion sort. Example 1: Input: 4->2->1->3  Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0  Output: -1->0->3->4->5 Java Program: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode insertionSortList ( ListNode head ) { ListNode dummy = new ListNode ( 0 ); ListNode curr = head , prevNode , nextNode ; while ( curr != null ) { //set the prevNode and n...

Home >> Interview Questions >> copy a linked list with random pointer Copy a Linked List with Random Pointer In this post, you will learn how to copy or clone a linked list with random pointer and its solution in Java.  A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.  Return a deep copy of the list not the reference of the original node. Example: Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]] Copy a Linked List with Random Pointer Java Solution Approach 1: Using HashMap - extra Space O(n). We can store all node as key and make new node as value. In the next loop can assign next and random pointer to the copied nodes. Java Program:  /* // Definition for a Node. class Node { public int val; public Node next; public Node random; public Node() {} ...

Home >> Interview Questions >> Flatten a Multilevel Doubly Linked List Flatten a Multilevel Doubly Linked List Solution In this post, you will learn how to flatten a multilevel doubly linked list in Java. You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.  Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. Example: Input:  1---2---3---4---5---6--NULL          |          7---8---9---10--NULL                |               11--12--NULL ...