Given a singly linked list, reverse it. For example:
Input:
1->2->3->4->5
Input:
5->4->3->2->1
This problem is never asked standalone in an interview but very important to answer a few of the questions which are commonly asked in Amazon and Facebook interviews like reverse K nodes in a linked list or reverse K alternating nodes.
The idea to reverse a linked list is simple, you take each node, make it point to its previous node, and go to the next node. For each node, we need to maintain three different pointers: current which points to the node we are working on, prev, the node which is immediately previous to the current node and next, the node which is immediately next to the current node.
How do we change the pointers? If we change current.next to point to previous node, we cannot go forward. So, the first thing to secure if that we can move forward, by storing current.next to next.
Now, that we have secured the next pointer, we can change current.next to point to the prev. As we will be moving forward to the next node, the new previous node will be the current node, change prev to current.
The last step, move forward, make current as next.
Here is an example of reversing a linked list
Keep doing this till we have no nodes remaining in the linked list. What should we return now? current, prev or next? When current is at the null, next would already be null and we cannot return a null value of a linked list which was non-null, right? Only pointer which now points to the last node is prev and should be returned.
There is another confusion and that is how to initialize these three pointers. Which node you will process first? The head. So, the current should be initialized to the head of the linked list. What would be the next pointer of the head in the reversed linked list? It will be null. Initialize prev as null. For next it does not matter, you can choose to initialize it with null or null.
Reverse a linked list implementation
package AlgorithmsAndMe;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class ReverseLinkList {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode next = head;
ListNode current = head;
while(current != null){
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
}
The time complexity of reversing a linked list is O(n).
Given a number represented by a linked list, add 1 to that number and return a new linked list. For example, if the number is 2345, then it is represented as linked as shown below.
When we add one to 2345 represented by the linked list, the resulting linked list looks as follows.
Thought process
First of all, think if there is only one node in the linked list, that means the linked list represents a single-digit number. What will do? We will add 1 to the node.val and return a new node with the sum. This is our smallest case, however, there is a catch here as well. What if the single-digit number is 9. In that case, the sum is 10 and since every node contains only a single digit of the number, we can store 0 in the new node. What happens to 1? We can treat that 1 as a carry.
Now, there are no digits present to add carry to (remember we had only one node linked list), we will create a new node and put carry in that and then linked the carry node to the previous node with 0.
This is a very important case which we learned here. When you have processed all the nodes of the linked list, if the carry remains, create a new node and attach it to the head of the list. Most of the students make a mistake in this case.
How about when there is more than one node in the linked list? In that case, 1 is added to the node in the end and carry is propagated, if any, backward till head. Next question, how can you process the last node of the linked list and move backward? Well, remember how we print a linked list in the reverse order. We go deep in the linked list till the last node and use recursion unfolding to come backward. We can use the same concept. Go to the last node recursively, maintain a carry and move backward till the head. Once, you have processed head node, check if carry is non zero, if it is, creates a new node and attach it at front.
Show me the implementation
package AlgorithmsAndMe;
import java.util.List;
public class PlusOne {
int carry = 0;
public ListNode addOneToLinkedList(ListNode head){
ListNode newList = addOneToLinkedListUtil(head, 1);
if(carry > 0){
ListNode newNode = new ListNode(carry);
newNode.setNext(newList);
return newNode;
}
return newList;
}
public ListNode addOneToLinkedListUtil(ListNode head, int val){
if(head == null) return null;
if(head.getNext() == null){
return createNode(head, val);
}
ListNode returnedNode =
addOneToLinkedListUtil(head.getNext(), val);
ListNode newNode = createNode(head, carry);
newNode.setNext(returnedNode);
return newNode;
}
private ListNode createNode(ListNode node, int val){
int newVal = node.getValue() + val % 10;
carry = (node.getValue() + val) / 10;
return new ListNode(newVal);
}
}
The complexity of the code is O(n), we will be processing each node at least once. The tricky part is space complexity, as recursion takes implicit stack memory, the space complexity is also O(n).
This code creates a new node, what if we new list does not have to be created and we have to return the same list back. The below code implements the PlustOne such that it returns the same list back.
package AlgorithmsAndMe;
import java.util.List;
public class PlusOne {
public ListNode addOneToLinkedList2(ListNode head){
int c = addOneToLinkedListUtil2(head);
if(carry > 0){
ListNode newNode = new ListNode(carry);
newNode.setNext(head);
return newNode;
}
return head;
}
public int addOneToLinkedListUtil2(ListNode head){
if(head == null) return 1;
int sum = head.getValue()
+ addOneToLinkedListUtil2(head.getNext());
head.setVal(sum % 10);
return sum / 10;
}
}
Given a singly linked list, reverse every K nodes of the linked list and return the head of the modified linked list. k is a positive integer.
Good clarifying question: If the number of nodes is not a multiple of k then the last nodes should remain as it is.
Example:
Input:
List = 1->2->3->4->5
K = 2
Output:
2->1->4->3->5
Input:
List = 1->2->3->4->5
K =
Output:
3->2->1->4->5
Reverse K nodes in list: thought process
If I have two chunks of k nodes, one after the other, how would I reverse them in chunks of k nodes? Well, I will first reverse the part which is at the end, return the new head of the reverse part, then I will reverse the first part. Now the most important part, how would I link the first and second parts?
The head of the first part should be the last node of the reversed list, right? The last node of the first part should link to the head of the second part to link these two chunks together.
How can we implement it using recursion? From the above explanation, we know that we have to chunk the linked list into parts with k nodes each till we cannot further divide it. Once we reach the last k nodes part, we apply the method above. Reverse the chunk and return the head of the reversed chunk.
Take care of the last chunk, as it may have less than nodes, in that case, we will return the head of that chunk without reversing the chunk as per the question demands.
It is very important that you know how to reverse a linked list to solve this problem. If you have doubts, I recommend reading that first.
Reverse K nodes : Implementation
public ListNode reverseKGroup(ListNode head, int k) {
//This is head of current chunk
ListNode currentHead = head;
//Move k nodes;
ListNode current = head;
for(int i=1; i< k && current != null; i++){
current = current.next;
}
if(current != null){
//Reverse the remaining link list and get the head.
ListNode reverseHead = reverseKGroup(current.next, k);
//Now reverse the current k nodes list.
current = head;
ListNode prev = null;
ListNode next = head;
int count = 1;
while(current != null && count <= k){
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}
//Link the head with the returned head
currentHead.next = reverseHead;
/*Return the new head, which is last
node of the current of current k nodes */
return prev;
}
//If there are less than k nodes in last chunk
else return head;
}
The time complexity of the implementation is O(n) where n is number of nodes in the list.
Swap 2 nodes in a linked list
In this problem, we have to reverse every pair of nodes in the linked list. For example:
Input:
list = 1->2->3->4->5->6
Output:
2->1->4->3->6->5
This problem is a special case of the above problem of reversing K nodes in a linked list, here k is 2, however, can be implemented in an easier way.
Implementation
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
ListNode temp = head.next;
ListNode next = head.next.next;
//Reversing the pair
temp.next = head;
head = temp;
//Reverse the remaining list.
temp.next.next = swapPairs(next);
return head;
}
The time complexity of the implementation is O(n) where n is number of nodes in the list.
We learned a lot about linked and solve around 30 odd problems : Linked list problems. However, the actual implementation of a linked list in Linux kernel is very different than what we learned. Let us understand how a linked list is implemented in Linux kernel and used in kernel code.
In a simple linked list, nodes contain data and point to the next node in the linked list. In other words, its the list which contains nodes which are linked. A typical example of the structure of a node of this kind of a list is:
class Node {
private int data;
private Node next;
public Node (int data, int next){
this.data = data;
this.next = next;
}
//Getters
};
However, linked lists in the Linux kernel, it’s the other way around, that is linked list is contained inside the node. This means, that there is no next pointer inside the node and each node is effectively a head node like a circular linked list. Also, it is a doubly linked list. A lot of things in one sentence!!
Linked list implementation in Kernel
Let’s understand it in detail. As said above, linked list is contained inside the node, structure of node is like this:
struct node {
int data;
list_head list; // list is inside the node
};
See it has two pointers, essentially, making any node which contains this structure, part of a doubly linked list. The most interesting part of this kind of definition of a node is that same node can be part of multiple lists without being reallocated for each list. For example, in traditionally linked lists, if we need two linked lists: one as odd numbers and other as prime numbers, we would have to define two linked lists, one with odd numbers and other with prime numbers. With implementation provided in the Linux kernel, we can attach the same node to two lists as shown below, where an odd number which is also prime is allocated only once.
struct numbers {
int number;
list_head odd_numbers; // contains all odd numbers
list_head primer_numbers; // Contains all prime numbers
};
How to access a node in list in Linux Kernel
We understood the node structure, how can we access a given node of a linked list. It was simple to do in a normal linked list as the base address of node accessible. In list implemented in Linux kernel, we have a pointer to the list_head structure in the next node and not a pointer to next node itself, as shown below.
There is a beautiful trick in C, which is used here to access the base address of the node whose list_head pointer is given. Once the base address of a node is known, accessing the node becomes similar to a normal linked list. The trick is that given a pointer to list_head in the structure; to find the base pointer of structure, find the offset at which list_head is stored in list. Once, we know the offset, (how many bytes, it is far from base address), then just subtract that offset from the absolute address of the pointer (which is given) and we get the base address. Figure explains
Let’s take an example, we will use structure numbers as given above. To get offset of element number in that, code is:
(unsigned long)(&((struct numbers *)0)->number)
Now, that we have offset of number and absolute address of number, we can get the base address of struct numbers as:
ANSI C defines the offsetof() macro in which lets you compute the offset of field f in struct s as offsetof(struct s, f). If for some reason you have to code this sort of thing yourself, one possibility is
In last post : Linked list data structure, we discussed basics of linked list, where I promised to go in details what is difference between array and linked list. Before going into post, I want to make sure that you understand that there is no such thing called one data structure is better than other. Based on your requirements and use cases, you chose one or the other. It depends on what is most frequent operation your algorithm would perform in it’s lifetime. That’s why they have data structure round in interview process to understand if you can chose the correct one for the problem.
What is an array? Array is linear, sequential and contiguous collection of elements which can be addressed using index.
What is a linked list? Linked list is linear, sequential and non-contiguous collection of nodes, each node store the reference to next node. To understand more, please refer to Linked list data structure.
Difference between arrays and linked list
Static Vs dynamic size
Size of an array is defined statically at the compile time where as linked list grows dynamically at run time based on need. Consider a case where you know the maximum number of elements algorithm would ever have, then you can confidently declare it as array. However, if you do not know, the linked list is better. There is a catch : What if there is a rare chance that number of elements will reach maximum, most of the time it will be way less than maximum? In this case, we would unnecessary allocating extra memory for array which may or may not be used.
Memory allocation
An array is given contiguous memory in system. So, if you know the address of any of the element in array, you can access other elements based position of the element.
Statically allocated contiguous memory
Linked list are not store contiguous on memory, nodes are scattered around on memory. So you may traverse forward in linked list, given node (using next node reference), but you can not access nodes prior to it.
Dynamically allocated non-contiguous memory
Contiguous allocation of memory required sufficient memory before hand for an array to be stored, for example if want to store 20 integers in an array, we would required 80 bytes contiguous memory chunk. However, with linked list we can start with 8 bytes and request more memory as when required, which may be wherever. Contiguous allocation of memory makes it difficult to resize an array too. We have to look for different chunk of memory, which fits the new size, move all existing elements to that location. Linked list on other hand are dynamically size and can grow much faster without relocating existing elements.
Memory requirement
It’s good to have non-contiguous memory then? It comes with a cost. Each node of linked list has to store reference to next node in memory. This leads to extra payload of 4 bytes in each node. On the other hand, array do not require this extra payload. You have to trade off extra space with advantages you are getting. Also, sometime, spending extra space is better that have cumbersome operations like shifting, adding and deleting operation on array. Or value stored in node is big enough to make these 4 bytes negligible in analysis.
Operation efficiency
We do operations of data structure to get some output. There are four basic operations we should be consider : read, search, insert/update and delete.
Read on array is O(1) where you can directly access any element in array given it’s index. By O(1), read on array does not depend on size of array. Whereas, time complexity of read on linked list is O(n) where n is number of nodes. So, if you have a problem, which requires more random reads, array will over-weigh linked list.
Given the contiguous memory allocation of array, there are optimized algorithms like binary search to search elements on array which has complexity of O(log n). Search on linked list on other hand requires O(n).
Insert on array is O(1) again, if we are writing within the size of array. In linked list, complexity of insert depends where do you want to write new element at. If insert happens at head, then it O(1), on the other hand if insert happens at end, it’s O(n).
Insert node at start of linked listInsert node at the tail of linked list
Update means here, changing size of array or linked list by adding one more element. In array it is costly operation, as it will require reallocation of memory and copying all elements on to it. Does not matter if you add element at end or start, complexity remains O(1). For linked list, it varies, to update at end it’s O(n), to update at head, it’s O(1). In same vain, delete on array requires movement of all elements, if first element is deleted, hence complexity of O(n). However, delete on linked list O(1), if it’s head, O(n) if it’s tail.
To see the difference between O(1) and O(n), below graph should be useful.
Complexity analysis graph
Key difference between array and linked list are as follows
Arrays are really bad at insert and delete operation due to internal reallocation of memory.
Memory allocation is contiguous, which make access elements easy without any additional pointers. Can jump around the array without accessing all the elements in between.
Linked list almost have same complexity when insert and delete happens at the end, however no memory shuffling happens
Search on linked list is bad.=, usually require scan with O(n) complexity
Dynamically sized on run time.
Memory allocation is non-contiguous, additional pointer is required to store neighbor node reference. Cannot jump around in linked list.
Please share if there is something wrong or missing. If you wan to contribute to website, please reach out to us at [email protected]
Linked list is a very important data structure to understand as lot of problems are asked based on linked list in Amazon, Microsoft and Google interview. Today, we will understand the basics of linked list data structure and it’s implementation.
Linked list represent linear sequence of elements. Each element connected to next element using chain of references. Another data structure which store linear sequence of items is array. There are some advantages and uses cases where linked list way of storing sequence is more efficient than array, I will cover that into next post : Arrays Vs Linked lists.
In last paragraph, I emphasized on linkedlist being linear data structure. In linear data structure, there is a sequence and order how elements are inserted, arranged and traversed. In order to go to tail of linked list, we have to go through all of the nodes.
linear data structure when elements can be traversed only in one order
Non linear data structures are the ones where elements are not arranged or traversed in a specific order. One element may be connected to many others, hence we cannot traverse them in the same order every time. Example of non-linear data structure would be maps, dictionaries, trees, graphs etc.
Non linear data structure when nodes cannot be traversed in one order always
Linked list implementation
Linked list consists of node, any number of nodes. Each node contains two things : first, value of the node, this value can be of any type, integer, string, or other user defined type. Second, a reference which points to next node in linked list. A node can be declared as follows:
What happens if the node is last node in linked list? At last node, next pointer of the node points to the null. It’s very important to understand this bit, as this condition will be used on almost every problem you have to solve on linked list.
Linked list is dynamic data structure. By dynamic data structure, we mean, it’s size and nature is not defined at the time of compilation, but defined at run time. Every time, a new node is added to linked list, new memory location is allocated and previous node’s next pointer will point to new node.
Operations of linked list
Adding node at the end of list There are three basic steps to add a node to linked list at end:
Check if there is already a node
If no, then create a new node and return it as head of linked list.
If there is a node,
Scan through linked list using next pointer, reach to the last node.
Create a new node, and point next pointer of last node to this new node.
Node * createNode(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}
void addNode(Node **headRef, int value){
//create new node
Node *newNode = createNode(value);
//find the last node
Node *currentNode = *headRef;
while(currentNode && currentNode->next != NULL){
currentNode = currentNode->next;
}
if(currentNode)
currentNode->next = newNode;
}
else{
//Change headRef to point to new head.
*headRef = newNode;
}
}
Complexity of adding a node to linked list is O(n).
Insert node at head of list In this case too, we allocate a new node, however, this time we do not have to scan the entire list. Every time we add node to list, it’s head changes though.
Check if there is already a node
If no, then create a new node and return it as head of linked list.
If there is a node,
Create a new node, and point next pointer new node to head.
It’s very important to understand that linked list is a recursive data structure. Base case is a linked list with no node, represented by NULL node. Every problem on linked list can be solved using template : process one node, and then recursively process the remaining linked list.
In programming terms, linked list is divided into two parts, head and tail. The node being processed is called head and rest of the linked list is tail. Tail has the exactly same structure as the original list.
Problems like merging linked lists, reverse a linked list, find length of linked list all can be solved using the same template of processing one node and the recursively call function on remaining node.
Types of linked list
There are three types of linked lists : 1. Singly linked list Singly linked lists contain nodes with data and reference, i.e., next, which points to the next node in the sequence of nodes. The next pointer of the last node will point to null. In singly linked list you can traverse only in one direction.
singly linked list
2. Doubly linked list In a doubly linked list, each node contains two links – previous, which points to the node before current node and next, which points to next node. The previous pointer of the first node and next pointer of the last node will point to null. In doubly linked list, you can traverse it both directions. Two references adds to weight as extra memory is required.
doubly linked list
3. Circular linked list In circular linked list, next pointer of the last node will point to the first node. A circular linked list can be both singly as well as doubly linked list.
Circular doubly linked list
This was all for basics of linked list, I know problems on them are hard to solve but if you look at all the problems, they boil down to one thing : understanding of node and how recursion can be used. In next posts, we will be solving many of these problems and see how we can use these basics.
Please share if there is something wrong or missing. If you are interested in contributing to website and share your knowledge with thousands of users across world, please reach out to us at [email protected]
Given a linked list with every node has two pointers: next and random, ask is to clone this linked list with a random pointer to a new linked list.
The linked list will look like:
This problem can be solved using n extra spaces where we store a mapping of the existing node and new node in a hash map, then go through the linked list again, find the copy node of the current node, find copy node for its next, and link them. Then find the random pointer node of the current node, find the corresponding clone node of the random node, and link random pointer of the current nodes copy node to cloned random node. It takes 2 scans of the linked list as well.
However, the challenge is to do it in O(1) space complexity.
Thought process
We are using hashmap to know the corresponding cloned node of a node in the linked list, can we do that without using hashmap? Can we use the linked list itself to store the information?
The idea here is to add the cloned node after the original node in the given linked list. For each node, we will insert the cloned node between the original node and its next node. After inserting the nodes as a subsequent node of the original node, we can easily get the mapping we were storing in the hashmap right?
Once, all the nodes are linked together, we can copy the random pointer of the original node to the random pointer of the cloned node as
node.next.random = node.random.next
The last step will be to separate the two lists. We go through the list, for each node, we will get the cloned node by node.next, next of the current original node should be the next of the cloned node.
Last, we have to link the cloned nodes next to node.next.next and move forward to the next node of the original node.
Overall, this implementation required 3 passes to the linked list, first to insert nodes in between, then to copy the random pointers and then to detach the cloned linked list. Pass 2 and 3 can be combined but it is easier to understand that way.
Show me the implementation
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
Node current = head;
if(head == null) return null;
/* Step 1. create clones of each node and
insert them next to the original node.
List [1,2,3] will look like [1,1,2,2,3,3]
*/
while(current != null){
//create node.
Node newNode = new Node(current.val);
//Insert to the next of current
newNode.next = current.next;
current.next = newNode;
current = newNode.next;
}
/* Step 2. Copy the random pointers.
The cloned node's random will point to the
next of the original node.
*/
current = head;
while(current != null){
if(current.random != null){
//current.next is cloned node. it's random points
//to next of current node's random.
current.next.random = current.random.next;
}
current = current.next.next;
}
current = head;
Node newHead = head.next;
/* Step 3 : Detach the cloned list from the original list */
while(current != null){
Node node = current.next;
current.next = current.next.next;
//IMPORTANT: Check for the last node.
if(current.next != null){
node.next = current.next.next;
}
current = current.next;
}
//Return new head
return newHead;
}
}
The time complexity of above implementation is O(N) and space complexity is O(1)
First of all, what is a palindrome linked list? A linked list is palindrome if you get the same output by traversing it from head to tail or tail to head. For example, below linked list is a palindrome linked list as forward traversal is same as reverse traversal : 3,4,5,5,4,3
palindrome linked list
Where as this linked list is not palindrome for obvious reasons.
Non palindrome linked list
Given a singly linked list, find if linked list is palindrome or not.
This problem will give us more understanding on how to iterate over singly linked list as well as how to handle linked lists in recursive functions.
If linked list is palindrome : thoughts
What will be the brute force solution for the problem? We can scan the linked first and store the output in an storage. Then we reverse the linked list, and see if order of elements is same as what was in previous traversal.
Complexity of brute force solution is O(n), however, it requires three full traversals of linked list; first forward traversal, then to reverse linked list and then reverse traversal. Also, it require additional O(n) space.
We can put half of the linked list on stack. Traverse remaining half, for each node, same time, pop the node from stack, if data is equal, move forward, else return false. If you reach the end of linked list with stack empty, linked list is palindrome. Complexity is O(n) with additional space complexity of O(n).
Scan till middle of linked list and push all elements in stack
Now, pop the element from stack as we move in linked list. If they are equal, continue else return false
Next node is popped and compared
we reached the end of linked list and stack is empty. Hence, linked list is palindrome
What can be better? We are interested in if only half of the linked list, rest half have to be checked w.r.t to first half we they are same of not.
If we divide linked list in two halves exactly at the middle, and reverse first half, then if all the nodes from middle node to end are same as middle to start node, linked list is palindrome.
We have to reverse only half of the linked list.
We traverse linked list to find the size, then reverse half the list, traverse again to check if first half is same as latter half. You have to take middle based on the fact if size of linked list odd or even. Actually, you can avoid calculating the size, by following the hare and tortoise algorithm to find middle of linked list. Overall complexity is O(n) with no additional space required.
Implementation
#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node * next;
} Node;
Node * createNode(int val){
Node * temp = (Node *)malloc(sizeof(Node));
if(temp){
temp->data = val;
temp->next = NULL;
}
return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
Node * newNode = createNode(data);
newNode->next = *headRef;
*headRef = newNode;
}
void printList(Node *head){
while(head){
printf("%d->", head->data);
head = head->next;
}
printf("Null");
}
/* We are returning next node as it will be required
in calling function */
Node * reverseList(Node *node){
Node *current = node;
Node *prev = NULL;
Node *next = node;
while(current){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
int isPalindromeList(Node *head){
if(!(head && head->next)) return true;
Node *current = head;
Node *fast = head;
Node *prev = NULL;
Node *midNode = NULL;
/* We are finding the middle node.*/
while(fast && fast->next){
fast = fast->next->next;
/* We are saving previous node because
that will be end of fist list
in case of even number of nodes */
prev = current;
current = current->next;
}
/*Check if there are odd number of nodes, if fast pointer is
null, then there are even number of nodes,
else it's odd number
*/
if(fast){
midNode = current;
current = current->next;
}
//Let's reverse second half of list
Node *reversedSecondHalfHead = reverseList(current);
//Terminate first linked list
prev->next = NULL;
int isPalindrome = compareTwoLinkedLists(head,
reversedSecondHalfHead);
//Reverse back second half
current = reverseList(reversedSecondHalfHead);
//If there are odd number of nodes, midNode should not be null
if(midNode){
prev->next = midNode;
midNode->next = current;
}
else
prev->next = current;
return isPalindrome;
}
int main(void) {
Node *head = NULL;
push(&head, 3);
push(&head, 4);
push(&head, 5);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
printf("\nOriginal list :");
printList(head);
printf("\nIs list palindrome : %s", isPalindromeList(head)
? "true" :"false");
return 0;
}
Is palindrome linked list : recursive solution
To check if string is palindrome, standard way is to keep two pointers (i and j), i moving from left to right and j moving from right to left. We check if character at i and j match or not. If they don’t match, string is not palindrome. If i and j cross each other, string is palindrome. Can we apply above algorithm on linked list? No, because we cannot move backward in singly linked list. So what is the way? How about simulating the stack using recursive function.
We use two pointers, forward and backward, we move backward pointer ahead till we reach the end of linked list, that will be the terminal condition of recursive function. At any given time after hitting the terminal condition, forward and backward pointers will be n nodes from start and end respectively, where n varies from 0 to n. We check if content of both pointers are equal or not, if not, then linked list is not palindrome, if yes, linked list is palindrome till those nodes.
Palindrome linked list : implementation
#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node * next;
} Node;
Node * createNode(int val){
Node * temp = (Node *)malloc(sizeof(Node));
if(temp){
temp->data = val;
temp->next = NULL;
}
return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
Node * newNode = createNode(data);
newNode->next = *headRef;
*headRef = newNode;
}
void printList(Node *head){
while(head){
printf("%d->", head->data);
head = head->next;
}
printf("Null");
}
int isPalindromeUtil(Node **forward, Node *backward){
//There are no nodes is lists
if(!backward) return true;
/*we are recursing moving backward pointer ahead. Backward
pointer will start moving backward once we hit
above terminal condition of recursion */
int isPalindrome = isPalindromeUtil(forward, backward->next);
if(!isPalindrome) return isPalindrome;
/*At this point forward is n nodes ahead from start and
backward n nodes away from end n varies from 0 to n
Compare forwad and backward
*/
if((*forward)->data != backward->data){
return false;
}
//Move ahead forward pointer, backward will move back
automatically due to recursion
*forward = (*forward)->next;
return isPalindrome;
}
int isPalindromeListRecursiveMethod(Node *head){
/* we are starting with forward pointer and backward at head.
Notice that we passing reference to forward and just pointer
for backward pointer */
return isPalindromeUtil(&head, head);
}
int main(void) {
Node *head = NULL;
push(&head, 3);
push(&head, 4);
push(&head, 5);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 2);
printf("\nOriginal list :");
printList(head);
printf("\nIs list palindrome : %s",
isPalindromeListRecursiveMethod(head) ? "true" :"false");
return 0;
}
Complexity of algorithm to check if linked list is palindrome or not is O(n).
Please share if there is something missing or wrong. If you are interested in receiving study material for your interview preparation, please signup on Algorithms and Me mailing list.
Write a program to delete a node from a linked list. For example, in the linked list shown below, if we were asked to delete node 5, the result will be the linked list as shown.
To delete a node from the linked list, first, we need to find the node with the given value. We compare given value with the value of each node of the list; if the values match, we found the node to delete. To delete a node in a singly linked list, next pointer of the previous node of current node will point to next node of the current node. previous->next = current->next
However, if we are matching the value of the node with the given value as mentioned above, we don’t have access to the previous node of the current node.
So what shall we do? There are two ways we can solve this problem: First, we compare the value of next of the current node instead of the current node, that way we are at the previous node of the node to be deleted when the match happens. Second, keep track of the previous node while traversing the linked list forward.
The node to be deleted can be anywhere in the linked list, there are three possibilities:
Node to be deleted is the head node of linked list.
Node to be deleted is any of the middle nodes.
Node to be deleted is last node of linked list.
In the first case, we should also update head pointer of the linked list. For second and third cases, we can just change the pointers: next of the previous node points to the next of the current node).
package com.company;
/**
* Created by sangar on 14.10.18.
*/
public class LinkedList<T> {
private Node<T> head;
public LinkedList(){
head = null;
}
public void insert(T data){
//If this is the first node to insert
if(this.head == null){
this.head = new Node<>(data);
}
else{
Node current = this.head;
/* Defensive programming, just in case current is null
* As we check null condition for head earlier, it should
* not be null in this while loop ever though
* */
while(current != null && current.getNext() != null){
current = current.getNext();
}
//We are at the last node.
current.setNext(new Node(data));
}
}
public Node<T> get(T data){
/*
Base condition if there is no nodes,
return null
*/
if(this.head == null){
return null;
}
else{
Node current = this.head;
/* Defensive programming, just in case current is null
* As we check null condition for head earlier, it should
* not be null in this while loop ever though
* */
while(current != null && current.getData() != data){
current = current.getNext();
}
return current;
}
}
public void deleteNode(int val){
Node current = this.head;
Node prev = null;
while(current != null && (int)current.getData() != val){
prev = current;
current = current.getNext();
}
//Case where node to be deleted is head
if(current == this.head){
this.head = this.head.getNext();
return;
}
if(current != null){
prev.setNext(current.getNext());
}
//let the gc free the memory
}
public void printList(){
Node current = this.head;
while(current != null){
System.out.print(" " + current.getData());
current = current.getNext();
}
}
}
Delete a node from a linked list with a reference
Above implementation will not work if there are duplicate values in a linked list, we will delete the first node with the given value and it may not be always the node intended to be deleted. What if we were given the pointer or address to the node to be deleted?
One way is to scan through the linked list and find the node matching the pointer. We can do that by comparing current->next to the pointer given. If they are equal, we can link the current->next = givenNode->next.
Can we avoid the traversing of the linked list? Yes, we can. We know the pointer to the node, let’s say it is givenNode. If we copy value of givenNode->next node into givenNode->value, we can delete the givenNode->next node. Before deleting the node, we will link givenNode->next = givenNode->next->next.
This method will not work if the node to be deleted is the last node of the linked list. In that case, even if we avoid accessing the null node after the last node, we may not be able to touch previous node’s next pointer, which will point to a freed node once we delete the last node.
public void deleteNode(Node nodeToDelete){
Node current = this.head;
if(nodeToDelete == null) return;
if(nodeToDelete.getNext() != null){
//Copy data
nodeToDelete.setData(nodeToDelete.getNext().getData());
//Change pointer
nodeToDelete.setNext(nodeToDelete.getNext().getNext());
}
//let the gc free the memory
}
The complexity of both of the above algorithms to delete a node in a linked list is O(N) where N is the number of nodes in the linked list.
Please share if there is anything wrong or missing. If you are preparing for an interview, and want to have personalized coaching to guide you through it, please signup here for free interview preparation session.
Given two linked lists, we need to find out that if two linked lists merge, if yes, find the merge point.
For example, in the figure below, node(5) is the merge point of two linked lists.
How can we identify that two linked lists do not merge? Easy, if two linked lists merge at any given node including the last node, the last node should be the same. If the last nodes of two linked lists are different, we can safely say that two linked lists do not merge.
Merge point of two linked lists
How to find the merge point is the next problem. From the above diagram, notice that all the nodes after the merge point are the same if two linked lists are merged at a certain node. So that part of two linked lists is common to both.
We can use this insight to find the merge point. If lengths of two linked lists are equal, then we can just start traversal of those lists from heads and they will meet the merge point.
What if the lengths are different? In this case, there is an equal number of nodes in two linked list after the merge point. The difference has to be before the merge point. If we get the difference between the lengths and move the pointer on the longer list head by the difference, we will reach the merge point at the same time when we traverse lists again.
If the length of two linked lists is different, the problem reduces to the problem where we need to reach the end of two lists at the same time. There is a simple solution to that.
Implementation
#include<stdlib.h>
#include<stdio.h>
typedef struct node{
int data;
struct node *next;
} Node;
void print_list(Node * head){
while(head){
printf("%d->" , head->data );
head = head->next;
}
printf("NULL");
printf("\n");
}
int merge_point(Node *L1, Node *L2){
Node * current1 = L1;
Node * current2 = L2;
int count_1 = 0;
int count_2 = 0;
//If any one list is null, return false
if(!current1 || !current2 ) return -1;
//Count number of nodes in list 1;
while(current1->next){
count_1++;
current1 = current1->next;
}
// Count number of nodes in list 2
while(current2->next){
count_2++;
current2 = current2->next;
}
/*If last nodes of both linked list are not same,
linked list don't merge. */
if(current1 != current2)
return -1;
//Calculate the difference in lengths of linked list.
int diff = abs(count_1 - count_2);
//Move the longer linked list by diff number of nodes
if(count_1 < count_2){
Node * temp = L1;
L1 = L2;
L2 = temp;
}
current1 = L1;
current2 = L2;
while(diff && current1){
diff--;
current1 = current1->next;
}
// Now move both linked list till they meet at merge point
while(current1 != current2){
current1 = current1->next;
current2 = current2->next;
}
return current1->data;
}
void push(Node **head, int value){
if(*head == NULL){
(*head) = (Node *)malloc(sizeof(Node));
(*head)->data = value;
(*head)->next = NULL;
}
else{
Node * newNode= (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = value;
newNode->next = (*head);
*head = newNode;
}
}
}
void main(){
Node * L1 = NULL;
Node * L2 = NULL;
push(&L1,3);
Node * temp1 = L1;
push(&L1,4);
push(&L1,6);
push(&L1,7);
push(&L1,8);
push(&L1,9);
print_list(L1);
printf("\n");
push(&L2,5);
Node * temp2 = L2;
push(&L2,7);
push(&L2,8);
push(&L2,2);
push(&L2,1);
push(&L2,10);
printf("\n");
temp2->next = temp1;
print_list(L2);
int result1 = merge_point(L1, L2);
if(result1 != -1){
printf("\n Merge Point : %d", result1);
}
else{
printf("\n Lists don't merge");
}
}
The complexity of the algorithm to find merge point of two linked list is O(n), however, we scan the lists multiple times.
Please share if there is something wrong or missing. If you are preparing for an interview and want to have personalized coaching, please signup for a free demo session.
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Cookie settingsACCEPT
Privacy & Cookies Policy
Privacy Overview
This website uses cookies to improve your experience while you navigate through the website. Out of these cookies, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may have an effect on your browsing experience.
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.