Category Archives: Linked List

Merge a linked list into another linked list at alternate positions

Given two linked lists, insert nodes of second list into first list at alternate positions of first list. eg. 1->5->7->3->9 6->10->2->4, the first list should become 1->6->5->10->7->2->3->4->9 and second list should become empty. The nodes of second list should only be inserted when there are positions available. If the first list is 1->2->3 and second Read More →

Move last node to front in linked list

Write a C function that moves last element to front in a given Singly Linked List. For example, if the given Linked List is 1->2->3->4->5, then the function should change the list to 5->1->2->3->4. 1) Traverse the linked list till last node. 2) Use two pointers – one points to last node and other to Read More →

Swap every two nodes in a linked list

Given a singly linked list, swap every two nodes e.g. 1->2->3->4->5->6 should become 2->1->4->3->6->5 Solution: This can be done using two pointers. Take a current and temp pointer. At each iteration swap temp and current node. Repeat the steps until null node. You can think of the recursive solution of the problem. Implementation:

Delete alternate nodes of a Linked List

You are given a Singly Linked List.  Starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->4->8->10->15 then your function should convert it to 1->8->15 Solution: Steps: Take two pointers p and q Initially p points to head and q points to link of p Read More →

Frequency of a given number in a Linked List

You are given a linked list. You have to write a function that will give frequency of a given number in linked list. Here is a solution Algorithm: 1. Initialize count as zero. 2. Loop through each element of linked list: 3. If element data is equal to the given number then increment the count. Read More →

Copy a linked list with next and arbit pointer

original list

Problem: Given a doubly linked list with one pointer of each node pointing to the next node just like in a singly linked list. The second pointer(arbit pointer) however can point to any node in the list and not just the previous node. Write a program in to create a copy of this list. Algorithm: Read More →

Rotate linked list by K nodes

You are given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer. i.e. if the given linked list is: 1->2->3->4->5 and k is 3, the list should be modified to: 4->5->1->2->3. Assume that k is smaller than the number of nodes in linked list. Steps: Read More →

Reverse a singly linked list

How to reverse a singly linked list ? This problem demonstrates the ability to work with pointers and visualize a data structure. Here we are using two pointers to reverse a list. Time complexity will be O(n) as  you have to visit every node to change the pointers.

Singly Linked List – Delete Node

You are given a pointer to a node in a singly linked list. Delete that node from the linked list. Pointer to previous node is not available. Solution: The algorithm is as the following: We have a list looking like: … -> Node(i-1) -> Node(i) -> Node(i+1) -> … and we need to delete Node(i). Read More →

Write a function to get the intersection point of two Linked Lists (Y Shape)

Method 1 (Brute Force) Using 2 for loops. Outer loop will be for each node of the 1st list and inner loop will be for 2nd list. In the inner loop, check if any of nodes of 2nd list is same as the current node of first linked list. Time complexity of this method will Read More →

Write a program to detect loop in a Linked List

linkedlistLoop

Floyd’s Algorithm: This problem can be solved by using two pointers, slow pointer and fast pointer.Both these pointers will point to head of the linked list initially. Increment slow pointer by 1 node and the fast pointer by 2 nodes. If there’s a loop, the fast pointer will meet the slow pointer somewhere.We’ll discuss in Read More →

Insert nodes into a linked list in a sorted fashion

The solution is to iterate down the list looking for the correct place to insert the new node. That could be the end of the list, or a point just before a node which is larger than the new node. Note that we assume the memory for the new node has already been allocated and Read More →