Linked List

Question: Given a Linked List, we need to find the middle of the list and print the number. Input: 4, 8, 15, 16, 23, 42, 99 Output: 16 This is a very basic question and is a part of a bigger problem. However, there are several approaches to solve the above problem. BRUTE-FORCE APPROACH In this approach, we count the number of nodes in the list for each of the node and see whether it is the middle. Time Complexity: O(n2) Space Complexity: O(1) MORE SIMPLIFIED APPROACH In this approach,…

Question: Write a program to reverse a Linked List in pairs. That means we should reverse the 1st and 2nd numbers, 3rd and 4th numbers and so on. Input: 4, 8, 15, 16, 23, 42 Output: 8, 4, 16, 15, 42, 23 The basic idea behind solving this problem is that we need to traverse the entire list and we need to keep on swapping the values of 2 adjacent nodes. Since we need to reverse the values in pairs, it is also clear that we need to move 2…

Question: Given a Linked List, we need to find out if the number of nodes in the Link List are odd or even? Input: 4, 8, 15, 16, 23, 42 Output: EVEN The most easy method to solve this problem would be by traversing the entire Linked List and counting the number of nodes as we go. As the loop is finished, we can check if the count is even or odd. A Simpler Way: Another way of solving this problem in less time would be advancing 2 nodes at…

Question: Print the Linked List in reverse order. The actual structure of the Linked List must remain intact. Input: 4, 8, 15, 16, 23, 42 Output: 42, 23, 16, 15, 8, 4 We just discussed how to reverse a Linked List in an older post. Reverse a singly Linked List. But, in the above described method we changed the entire structure of the Linked List, the last node was no longer the last node and the head node had also changed. We might encounter cases, where we just need to…

Question: How will you reverse a singly Linked List? Input:– 4 -> 8 -> 15 -> 16 -> 23 -> 42 Output:– 42 -> 23 -> 16 -> 15 -> 8 -> 4 Reversing a singly Linked List is based upon a very simple concept. We just need to swap the “NEXT” value of each of the node, as we iterate over the list. That means that after the complete process, the first node should point to NULL, and the second last node should point to the first node…and so…

Question: Write a program to insert a node in a given sorted Linked List. Given List: 23 -> 32 -> 99 -> 101 -> 2222 Node to add:- 50 Output:- 23 -> 32 -> 50 -> 99 -> 101 -> 2222 To insert a node in a sorted Linked List, we need to perform a basic Linked List operation discussed in this post. Insert a node in a Linked List. In the given post, we knew the position at which we had to insert the node. But in this case…

Question: Suppose you are given a Linked List as 45-> 123-> 87-> 11-> 53-> 24-> 412-> 22. And we have to find the nth node from the end. Input:- n = 3 Output:- 24 BRUTE FORCE APPROACH:- In this method, start with the first node and count how many nodes are there after that node. If the number of nodes are < n-1, then return saying, “fewer number of nodes in the list.” If the number of nodes are > n-1 then go to the next node. Continue this until…

We covered some of the basic operations on a Linked List in this post. Basic operations on a Linked List However, in order to create a functional Linked List, we need even more operations before we can proceed further. Some of these operations are:- Inserting a node in the beginning of the Linked List. Inserting a node in the middle of a List. Inserting at a certain position Inserting after a specific node. Deleting a node from the Linked List. Deleting the entire Linked List. Inserting a node in the…

Here are some of the basic operations on a singly Linked List. Creating a new List Adding new elements Traversing a List Printing a List Basic functions to perform the above techniques have been defined in the code below. Creating a new list A new Linked List creation means that we do not have any elements in the list and we want to start fresh. This means allocating space in the memory for a node and then inserting the data into it. Since only a single node is created, the…

Linked List is a data structure used to store collections of data where successive elements are connected by pointers. It is really helpful to perform faster and memory efficient operations. This post gives you an introduction to all that with a video explanation.