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]Rearranging linked list first odd next even numbers
Posted on August 8, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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]Link list ADT
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
What is linked list?
Linked List consists of a sequence of nodes. These nodes are made-up of the following:
A Data Field for housing the data item
One or Two Reference/s for pointing at other node/s i.e. pointing to the next/previous node/s.
In this data structure, the nodes are allowed to be inserted and removed at any point in the list in constant time, however random access in not possible.
[Read More]Calculate length of the linked list that contains loop
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
In previous posts (Loop in a linked list and Calculate node that causes loop in a linked list) we discussed how to detect loop in a linked list and how to calculate node that causes loop in a linked list. In current post we discuss how to calculate length of the linked list when there is a loop in the linked list.
Following procedure explains how to calculate length of the linked list that contains loop:
[Read More]