Tag Archives: interview preparation for singly linked list

Alternating merge of two linked lists

Alternating merge of two linked lists Problem statement for alternating merge of two linked lists: Given two singly linked lists, you have to merge two linked lists alternatively. Alternating merge of two linked lists Examples: Consider two singly linked lists where List 1 has lesser nodes: 1-> 8-> 3-> 7-> NULL 5-> 3-> 9-> 13->… Read More »

Sort linked list whose alternate nodes are in ascending and descending order

Sort list whose alternate nodes are in ascending and descending order without using sorting techniques Problem statement to sort list whose alternate nodes are in ascending and descending order: Given is a singly linked list whose alternate nodes are sorted in ascending and descending order i.e. nodes at odd positions form an ascending ordered linked list… Read More »

Insertion sort on a singly linked list

Insertion sort list Problem statement for insertion sort list (linked list): Given a singly linked list, you have to apply insertion sort on linked list. Insertion sort list Example: Consider a singly linked list 3-> 7-> 2-> 8-> 1-> 9-> 9-> 5-> 6-> NULL After insertion sort, the resultant list should be 1-> 2-> 3-> 5->… Read More »

Sorted insert in linked list

Sorted insert in linked list Problem statement for sorted insert in linked list: Given a sorted singly linked list, you have to insert nodes into the linked list in sorted order. Sorted insert in linked list Example: Consider a sorted singly linked list 1-> 2-> 6-> 19-> 28-> NULL After inserting, say 10, resultant linked… Read More »

Quicksort a linked list

Quicksort a linked list Problem statement to quicksort list: Given a singly linked list, you have to apply quicksort on the linked list. Quicksort list Example: Consider a singly linked list 23-> 3-> 1-> 9-> 10-> 8-> NULL Resultant list should be 1-> 3-> 8-> 9-> 10-> 23-> NULL Algorithm to quicksort list: Partition Select… Read More »

Remove middle points from linked list of line segments

Removing middle points from linked list of line segments Problem statement to remove middle points of a line represented by a linked list: Given a singly linked list of coordinates in the form of (x,y) that represent points on a horizontal or vertical line, you have to remove all the middle points and represent the… Read More »

Removal of duplicate nodes from unsorted linked list

Removing duplicate nodes from an unsorted linked list Problem statement to remove duplicate nodes from unsorted linked list: Given an unsorted singly linked list, you have to remove duplicate nodes from it. Removing duplicate nodes from an unsorted linked list Example: Consider a singly linked list 3-> 7-> 1-> 9-> 9-> 6-> 7-> 8-> 2->… Read More »

Find point of intersection of linked lists

Find intersection point of two Y shaped linked lists – II NOTE: This post is an extension of Find point of intersection of linked lists. Problem statement to find intersection point of two linked lists: Given two singly Y-shaped linked lists, you have to find the intersection point. Point of intersection of linked lists Example:… Read More »

Find point of intersection of linked lists

Find intersection point of two Y shaped linked lists – I Problem statement to find intersection point of two linked lists: Given two singly Y-shaped linked lists, you have to find the intersection point. Point of intersection of linked lists Example: Consider two singly Y-shaped linked lists as shown. The point of intersection of linked… Read More »

Intersection of two sorted linked lists

Intersection of lists which are sorted Problem statement to find intersection of linked lists: Given two sorted singly linked lists, you have to form a new linked list containing the nodes common to both lists i.e. the new linked list is the intersection of the two given linked lists. Intersection of lists Example: Consider two sorted singly linked… Read More »