In this article, we have listed important Problems on Linked Lists which you must practice for Coding Interviews and listed introductory and background topics on Linked Lists as well. You must bookmark this page and practice all problems listed.
Table of Contents:
- Introductory topics in Linked List with Implementation (7)
- Types of Linked Lists (7)
- Practice Coding Problems on Linked List (50+)
- Research papers on Linked Lists (5)
Following is the list of Linked List Problems:
Introductory topics in Linked List with Implementation
- Singly Linked List: The most basic variant of Linked List
- Linked List implementation in C language
Covers implementation in C of various Linked List types like Singly Linked List, Doubly Linked List, Circular Linked Lists and others.
- Linked List implementation in Java language
- Linked List with no NULLs
This is an important topic that you must cover. In interviews at top companies like Google, you must implement Linked List without using NULL as this is the standard coding practice in Industry. This is not covered in any books.
Basic operations in a Linked List:
- Search an element in a Linked List
- Insertion operation in a Linked List
- Deletion operation in a Linked List
Types of Linked Lists:
These are the types of Linked Lists that are used in practice:
- Singly Linked List
- Doubly Linked List
- Skip List
Skip List is a variant of Linked List that allows faster search compared to linear time search in other variants of Linked Lists. This is a Probabilistic Data Structure.
- XOR Linked List
XOR Linked List is the memory efficient version of Doubly Linked List
- Circular Linked List
Some extra Introductory topics:
Practice Coding Problems on Linked List
These are Practice Coding Problems on Linked List which you must learn and practice to ace all problems in your Coding Interview at companies like Google (click on the topic to go to the respective article where the solution is explained in depth with implementation):
- Insert element in a sorted Linked List
- Insertion Sort a Linked List
- Merge Sort a singly Linked List
- Binary Search in a Linked List
- Sort a Linked List which is already sorted on absolute values
- Find the middle element of a singly Linked List
- Flattening a Linked List
- Reverse a linked list using 2 pointers technique using XOR operator
- Reverse alternate groups of K nodes in a Singly Linked List
- Detect a loop in a linked list (3 methods)
- Finding the length of a loop in linked list
- Cycle Detection Algorithms
- To check if the linked list is a circular linked list (2 methods)
- Reverse a doubly linked list in C++
- Implementing a Stack using an Array and Linked list
- Implement Queue using Linked List
- Check whether a Singly Linked List is Palindrome or not
- Check if Linked List is Empty
- Algorithm to check if a linked list is sorted
- Algorithm to detect and remove loop in a Linked List
- Move all occurrences of an element to end of linked list
- Move Last Element of Linked List to Front
- Move the first element of the linked list to the end
- Delete Middle Node from Linked List
- Intersection point of two linked lists
Research papers on Linked Lists
- "Skip Lists: A Probabilistic Alternative to Balanced Trees" (on cmu.edu, Published 1990, cited 1556) by William Pugh.
- "Maintaining order in a linked list" (on ACM, published 1982, cited 512) by Paul F. Dietz.
- "Shadowed management of free disk pages with a linked list" (on ACM, Published 1983) by Matthew S. Hecht and John D. Gabbe.
- "The linked list representation of n LIFO-stacks and/or FIFO-queues in the single-level memory" (on ResearchGate) by A. V. Sokolov and A. V. Drac.
- "An Efficient Implementation of Max Tree with Linked List and Hash Table" by Xiaoqiang Huang, Mark Fisher and Dan Smith.
With this article at OpenGenus and the practice of all the topics mentioned, you must have a very strong hold on Linked Lists and will be able to crack any problem.