Linked List

Insert a node in the given sorted linked list.

by

Objective: Given a linked list in which nodes are sorted in ascending order. Write an algorithm to insert a given node into the linked list so that all the nodes in the list will maintain the sorted order. Example:  Given Linked List:  -> 2, Insert node: 6 New List:  -> 2 -> 6 Given Linked … Read more

Merge K sorted Linked List – Using Priority Queue

by

Objective: Given, K sorted linked list, Write an algorithm to merge all the linked list into one linked list which will be also be sorted. Example: List 1: –>1–>5 List 2: –>4–>8 List 3: –>4–>6–>9 List 4: –>2–>7–>10 Merged Linked List: –>1–>2–>4–>4–>5–>6–>7–>8–>9–>10 Approach: Use Priority Queue Please read Priority Queue and Linked List if needed. … Read more

Least Recently Used (LRU) Cache – Using HashMap and Doubly Linked List | Set 1

by

Objective: Design and Implement a data structure Least Recently Used (LRU) Cache. Least Recently Used (LRU) Cache: You have given a cache (or memory) capacity. The cache will be filled with items you will access or look for it. The most recently accessed item will be at the top of the cache whereas the least … Read more

Implement Stack Using Linked List

by

Objective: Write an algorithm to implement Stack using Linked List. If you do not know about then for starters its abstract data type in which follows the principle of LIFO (Last-In-First-Out) which means the data goes in last comes out first to read about in detail please read this link Stack Approach: Solution is quite … Read more

Swap Nodes in pairs in a Linked List by changing links

by

Objective: Given a linked list write an algorithm to swap nodes in pairs by changing links . Earlier we have seen “Swap Every Kth node in a Linked List“, where we have seen how to swap nodes by actually swapping the nodes but In this article we will see how to swap nodes by changing … Read more

Reverse Alternative ‘k’ nodes in a Linked List.

by

Objective: Given a linked list and a number ‘k’, write an algorithm to reverse alternate ‘k’ nodes in the linked list. This problem was asked in the Microsoft and Amazon interviews. Example: Approach: Recursion is the key here. Solution will be quite similar to “Reverse a Linked List in groups of given size ‘K’” with … Read more

Reverse a Linked List in groups of given size ‘K’

by

Objective: Given a linked list and integer ‘k’, write an algorithm to reverse the linked list in groups of size ‘k’. Example: Approach: Earlier we have seen how to reverse a linked list, solution for reverse the linked list in groups of size will be extension of this solution. Reverse first ‘k’ nodes of the … Read more

Reverse The Doubly Linked List

by

Objective: Reverse The Doubly Linked List. Example: Approach: Every Node in a doubly linked list has next and previous pointer. Do the linear traversal of the linked list and keep swapping the next and previous pointers. At the end, make the last pointer as the head of the list. Complete Code:Run This Code This file … Read more

Swap Kth Node from the front with the Kth Node from the End

by

Objective: Given a Linked List and a number k, Swap Kth Node from the front with the Kth Node from the End Example: ->10->20->30->40->50->60->70 Swapping 1 Node from the Front and from the End ->70->20->30->40->50->60->10 Swapping 2 Node from the Front and from the End ->70->60->30->40->50->20->10  Swapping 3 Node from the Front and from the … Read more

Delete X Nodes After Y Nodes In a Linked List

by

Objective: Given a Linked List and x and y. Delete x number of nodes after y nodes from the start. Example: ->10->20->30->40->50->60->70->80->90->100->110->120 Deleted 4 Nodes after 5 Nodes ->10->20->30->40->50->100->110->120 Approach: We need two pointers. One pointer at one node prior to the nodes to be deleted. ( Move it by y starting from the head). … Read more

Merge Sort in a Linked list

by

Objective: Given a Linked List, Sort it using merge sort. Example: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Reference : Merge Sort in array As it Merge sort, we apply the same logic , Divide and Conquer. Find the length of the link list, say it is L. mid will be L/2. Now we need to divide … Read more

Merge a Linked list into another Linked List at Alternate Positions.

by

Objective: Given two linked lists, merge one list into another at alternate positions, if second link list has extra nodes, print them as well Example: 5 -> 10 -> 15 -> 20 ->25 -> null 3 -> 6 ->9 -> 12 ->15 ->18 ->21 -> null Output : 5 -> 3 -> 10 -> 6 … Read more