Reverse a linked list

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
reverse 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).

Plus One Linked List

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.

plus one linked list

When we add one to 2345 represented by the linked list, the resulting linked list looks as follows.

add 1 to linked list

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.

add one to linked list

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.

plus one linked list

plus 1 in linked list

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

In the next post, we will look at how to add two numbers represented by two linked lists.

If you are preparing for interview and looking for personalized coaching, please reach out to us on [email protected] or book a free session with us.

Reverse K Nodes In Linked List

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.

reverse k nodes in linked list
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.

Linked list implementation in Linux kernel

Linked list implementation in Linux kernel

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

Here list_head is what defined as :

struct list_head{
  struct list_head *next, *prev;
}

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.

linked list representation in linux kernel

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

node representation in linked list in linux kernel

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:

((struct numbers *)((char *)(pos) - \
          (unsigned long)(&((numbers *)0)->number)))

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

#define offsetof(type, f) ((size_t) \
 ((char *)&((type *)0)->f - (char *)(type *)0))

Above code is not portable and some compilers may have problems with it.

There are some MACROS which are defined in the linux kernel which are useful in dealing with linked lists. Below are some examples:

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&amp;((type *)0)-&gt;member)))
<pre>#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
	(ptr)-&gt;next = (ptr); (ptr)-&gt;prev = (ptr); \
} while (0)

Please refer to this file to understand various macros which are used in Linux kernel.

In next post, we will use these constructs and see how can we created a list, access it and delete a list.

Please share if there is something wrong or suggestion for improvements. Also, if you like the content, please share it.

Difference between array and linked list

Difference between array and linked list

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.

linked list vs arrays
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.

arrays vs linked list
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 list
Insert 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.

difference between array and linked list
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.
  • Statically sized at the compile time
  • 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 data structure

Linked list data structure

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.

linked list data structure
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.

linked list as data structure
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:

typedef struct Node {
	int data;
	struct Node * next;
} Node;
Node structure
Linked list

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:
  1. Check if there is already a node
    1. If no, then create a new node and return it as head of linked list.
  2. If there is a node,
    1. Scan through linked list using next pointer, reach to the last node.
    2. 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.
  1. Check if there is already a node
    1. If no, then create a new node and return it as head of linked list.
  2. If there is a node,
    1. Create a new node, and point next pointer new node to head.
    2. Return new node as head pointer.
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);
	newNode->next = *headRef;
	*headRef = newNode;
}

Linked list data structure problems

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
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
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 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]

Clone linked list with random pointer

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:
clone list with random pointer

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?
clone a linked list

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.

Node clonedNode = node.next;
node.next = cloneNode.next;

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)

Palindrome linked list

Palindrome linked list

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

is linked list palindrome
palindrome linked list

Where as this linked list is not palindrome for obvious reasons.

palindrome linked list
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).

is linked list palindrome
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 

if linked list is palindrome
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.

Delete node from linked list

Delete a node from linked 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.

delete node from linked list

delete a node in linked list

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.

    delete a node from linked list

    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.

    Merge point of two linked lists

    Merge point of two linked lists

    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.

    merge point of two linked list

    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.

    merge point of two linked lists

    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.