Skip to main content

Posts

Showing posts from April, 2018

Adding one to number represented as Linked List

In this post, we will discuss a method to add one to a number which is represented using nodes of the linked list.  This problem becomes very simple if the given linked list is considered to be doubly linked list as it is easier to add one to the number at the end of the linked list and traverse the list from backward direction till carry becomes zero. but if the given linked list is a singly linked list then we have to first reverse the given linked list and then add one to the first node. So considering our linked list is a simple linked list we follow the below steps. Algorithm : Reverse the linked list. Add one to the data field of the first node.  While carry is not zero keep adding carry to the next node's data field  if you reach the end of the linked list and the carry is not zero then we add a new node to the end of the linked list.  Reverse the final linked list and return the head node of the linked list. C++ Program Java program ...

Delete kth element from end of Linked List

In this post, we will discuss a method to delete the kth element from the end of the linked list. In order to delete the required node, we first need to find the kth element from the end of the linked list and then we can delete that element, so in one of the previous posts we have discussed a method to find kth element from the end of the linked list and In another post we have seen a method to delete node from linked list with the only pointer to that node, So combining the 2 methods we can delete the kth element from the end of the linked list. Have a look at the below posts for an explanation of the methods used in this post Finding kth element from the end of the Linked list  Deleting element from the Linked List with only pointer to that node   Algorithm :  Initialize 2 pointers first and second to head node  Move node first to the kth node from the start  Move both first and second node through the list till the first node reaches the last no...

Deleting node with single pointer Linked List

In this post, we will discuss a simple method to delete a node when we have only the pointer of the node to be deleted and no link to the head or tail node. Deleting node with the only pointer to that node is one of the famous and very easy interview questions and is asked a lot. The method we use can be used for both simple or doubly linked list. To delete the given node, we can use the following method Algorithm : Let the node to be deleted be called as the current node. Create a temp node to point to the next node. Now copy the contents of the temp node to the current node. copy the link field of the temp node to the link field of the current node. delete or free the memory pointer by the temp node . C++ Program Java program Python Program C++ Program Java Program Python Program Sample input and output to check the program You might also be interested in  Singly Linked List Double Linked List Linked Lis...

Finding kth element from end of Linked List

In one of my previous post I discussed a method to find the middle element of the linked list in single traversal using 2 pointers. In this post We will see a similar approach to find the kth element from the end of the linked list. Finding the kth element from the end of the linked list is one of the famous interview questions and is asked a lot. In order to find the kth element from the end of the linked list we use 2 pointers. Let the 2 pointers be first and second. now we initialize them to point at the head node of the linked list and move the second pointer to the kth node. After that we start traversing the linked list using both the pointer and keep moving them forward until the first pointer reaches the end of the linked list. as the difference between the position of the pointers is k places when the first node points the last node then the second pointer will point to the kth element from the end. So we can simply return the second pointer or the contents of the...