K reverse a linked list with increasing K
Posted on May 25, 2015
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Reverse k elements in the linked list such that k goes on increasing
Example
Eg. 1 - 2 - 3 - 4 - 5 - 6 - 7
output - 1 - 3 - 2 - 6 - 5- 4 - 7
Solution You can take this problem here. Here we are just increasing k.
public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) { ListNode<Integer> nextNode = headerNode.next; ListNode<Integer> startNode = null; ListNode<Integer> endNode = null; int k = 2; while (nextNode !
[Read More]Union and Intersection of two unsorted Linked Lists
Posted on July 30, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter.
Example Input: List1: 10->15->4->20 lsit2: 8->4->2->10 Output: Intersection List: 4->10 Union List: 2->8->20->4->15->10 Solution Method 1 - Simple
Following are simple algorithms to get union and intersection lists respectively.
Intersection (list1, list2)
Initialize result list as NULL. Traverse list1 and look for its each element in list2, if the element is present in list2, then add the element to result.
[Read More]Priority Queue based on Sorted Linked Lists
Posted on January 6, 2012
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Removing a loop in a singly linked list
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Problem:
Remove a loop from a singly linked list if the list has a loop.
Example
For example, 1->2->3->4->1 (4 points to the head node 1) should become 1->2->3->4 while 1->2->3->4 should stay the same 1->2->3->4.
Solution The problem has 3 steps :
Detect if there is a loop in the list (already solved here) Identify the start of the loop (already discussed here) Delete the loop, which we will discuss here.
[Read More]Concurrent Skip List
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Find common nodes from two linked lists using recursion
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
I have to write a method that returns a linked list with all the nodes that are common to two linked lists using recursion, without loops.
For example,
first list is 2 -> 5 -> 7 -> 10
second list is 2 -> 4 -> 8 -> 10
the list that would be returned is 2 -> 10
I am getting nowhere with this.. What I have been think of was to check each value of the first list with each value of the second list recursively but the second list would then be cut by one node everytime and I cannot compare the next value in the first list with the the second list.
[Read More]Y – shaped Linked List. Algorithm to find the node of intersection of two lists.
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem Find the node of intersection of 2 lists.
Example:
Solution Method 1 - Taking advantage of the link list length
Here is the pseudo code to find the node of intersection of 2 lists:
1) Go through L1 and get its length l1 2) Go through L2 and get its length l2 3) Now find the difference d = l1-l2 4) So d is the number of nodes that are extra in longer list.
[Read More]Remove duplicates from an unsorted linked list
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP: How would you solve this problem if a temporary buffer is not allowed?
**Example **
Input/Output
Original linked list:
2 -> 3 -> 2 -> 5 -> 2 -> 8 -> 2 -> 3 -> 8 -> null
After deleting duplicate node:
2 -> 3 -> 5 -> 8 -> null
We have already seen deleting duplicates from the sorted list.
[Read More]K – Reverse a linked list
Posted on January 2, 2012
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
This is one of the questions asked in Microsoft Interview.
Given a linked list, we need to write a function that reverses the nodes of a linked list ‘k’ at a time and returns modified linked list.
The following are the constraints given:
If the no. of nodes in a link list is not a multiple of k then left-out nodes in the end should remain as it is You have to retain the memory address of the nodes without modifying it i.
[Read More]Deleting a node from a singly linked link list
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Question: You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C.
Answer: To delete a node, you have to redirect the next pointer of the previous node to point to the next node instead of the current one. Since we don’t have a pointer to the previous node, we can’t redirect its next pointer.
[Read More]