Advice > Software engineering

40+ linked list questions and solutions (easy, medium, hard)

By Gareth Dwyer on September 06, 2021 How we wrote this article
Linked list interview questions

To ace your coding interview for a software engineering job, you’ll need to understand linked lists. They come up frequently in coding interviews and are fundamental to many other data structures too.

Let’s take a look at some typical linked list questions.

5 typical linked list interview questions
  • Given the head of a singly linked list, reverse the list, and return the reversed list.
  • Insert a node into a sorted doubly linked list.
  • Given the head of a linked list, determine if the linked list has a cycle in it.
  • Given the head of a sorted linked list, delete all nodes that have duplicate numbers.
  • You are given an array of “k” linked lists, with each linked list sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

Below, we take a look at some more questions and provide you with links to high quality solutions to them. We explain how linked lists work, their variations, and the most important things you need to know about them, including a useful “cheat sheet” to remind you of the key points at a glance.

This is an overview of what we’ll cover:

  1. Easy linked list interview questions
  2. Medium linked list interview questions
  3. Hard linked list interview questions
  4. Linked list basics
  5. Linked list cheat sheet
  6. Mock interviews for software engineers
Click here to practice coding interviews with ex-FAANG interviewers

1. Easy linked list interview questions

You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of linked lists.

As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.

If you get stuck, go ahead and look at the solutions, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.

Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the "phone screen" stage, so you should be comfortable answering them without being able to write code or use a whiteboard.

1.1 Merge two sorted lists
1.2 Linked list cycle
1.3  Intersection of two linked lists
1.4 Reverse linked list
1.5 Palindrome linked list
1.6 Delete node in a linked list
1.7 Middle of the linked list
1.8 Convert binary number in a linked list to integer
1.9 Remove duplicates from sorted list
1.10 Remove linked list elements
1.11 Insert a node at the tail of a linked list
1.12 Insert a node at the head of a linked list
1.13 Print in reverse
1.14 Reverse a doubly linked list
1.15 Inserting a node Into a sorted doubly linked list
1.16 Find merge point of two lists
1.17 Get node value
1.18 Compare two linked lists

2. Medium linked list interview questions

Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.

2.1 Add two numbers
2.2 Remove Nth node from end of list
2.3 Copy list with random pointer
2.4 Sort list
2.5 Odd even linked list
2.6 Rotate list
2.7 Reorder list
2.8 Swap nodes in pairs
2.9 Remove duplicates from sorted list II
2.10 Partition list
2.11 Reverse linked list II
2.12 Linked list cycle II
2.13 Insertion sort list
2.14 Linked list random node
2.15 Flatten a multilevel doubly linked list
2.16 Add two numbers II
2.17 Split linked list in parts
2.18 Next greater node In linked list
2.19 Remove zero sum consecutive nodes from linked list

3. Hard linked list interview questions

Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.

3.1 Design linked list
3.2 Merge k sorted lists
3.3 Reverse nodes in k-group
3.4 Design Skiplist

4. Linked list basics

In order to crack the questions above and others like them, you’ll need to have a strong understanding of linked lists and how they work. Let’s get into it.

4.1 What is a linked list?

A linked list is a data structure used to store a collection of data elements. In this way, it is similar to an array. However, unlike an array, the data elements in a linked list do not need to be stored contiguously in memory. Rather, each node in a linked list has a pointer or reference to the memory location of the next node in the list. This means that linked lists do not have a fixed size like arrays, and can easily grow and shrink as elements are added or removed.

what is a linked list?

Another advantage linked lists have over arrays is that inserting or removing elements from a linked list is possible in constant time, whereas removing or inserting elements into an array generally takes linear time. 

Since the data elements are not stored sequentially in contiguous memory, linked lists are not as efficient as arrays at random access of elements. Indexes are commonly used to access any element in an array in constant time. Accessing an element in a linked list generally means walking the list from one node to the next. This takes linear time.

4.1.1 Types of linked lists (Java, Python, C++)

There are a number of variations on the standard singly linked list. 

A doubly linked list has nodes with links to next and previous nodes, making it possible to traverse the list in either direction. 

A circular linked list's last node has a link to the list's first node. This is useful for implementing certain types of circular buffers. It is also useful for implementing round-robin-type schemes. 

A multi-linked list has multiple links from each node. The different links point to the “next” node based on some ordering or logical criteria. In this way, it is possible to have the list ordered on multiple properties. For example, in a movie list, there could be a link to the next movie alphabetically, another link to the next movie chronologically, and another link to the next movie by the same director. Multi-linked lists are also useful for implementing sparse matrices, where a node has a link to the next number in the row, and the next number in the column.

Java has a built-in linked list implementation called "LinkedList." Python has a "deque" class in its collections module, which is implemented as a linked list. In the Standard Template Library (STL) in C++, there is a linked "list" class, which implements a doubly linked list.

4.1.2 How linked lists store data

Linked lists are made up of a string of nodes. Each node is a container which stores the data element along with a reference to the next node. The first node is known as the head of the list. This is often used as the entry point, or handle, to the linked list. The last node in the list generally has its next pointer set to null, except in circular linked lists, where the last node points to the head node. 

4.1.3 How linked lists compare to other data structures

Linked lists are mainly contrasted to arrays. Arrays have faster access time, in constant time, to access a random element through indexes. Accessing an element in a linked list takes linear time. Linked lists are faster at inserting and removing elements, which can be done in constant time if the target position of the node is known, whereas arrays take linear time. Linked lists can also grow to very large sizes more easily than arrays, as linked lists are not bound to available contiguous memory blocks as arrays are. 

Queues and stacks are often implemented using linked lists, as the size of these structures is often large and dynamic. Queues and stacks also do not require random indexed access to elements, as elements are added and removed from the ends. Linked lists perform well here, as adding or removing elements from the ends of the list can be done in constant time.

Need a boost in your career as a software engineer?

If you want to improve your skills as an engineer or leader, tackle an issue at work, get promoted, or understand the next steps to take in your career, book a session with one of our software engineering coaches.

5. Linked list cheat sheet

Linked list definition:  A linked list is a collection of nodes representing a sequence. Each node contains data and a reference (a link) to the next and/or previous node in the sequence.

Linked lists cheat sheet
 

You can download this cheat sheet here.

Related algorithms and techniques

5.2 Cheat sheet explained

The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.

The cheat sheet is broken into time complexity (the processing time for various linked list operations) and algorithm complexity (the amount of time and space used for common algorithms).

For more information about time and space requirements of different algorithms, read our complete guide to big-O notation and complexity analysis.

5.2.1 Linked list time complexity

The important point to remember when considering time complexity with linked lists is that accessing or finding a random element in a linked list takes linear time, or O(n), whereas adding or removing a known element takes constant time. This is the inverse of an array’s time complexity, and understanding this will help you with questions about where to use a linked list vs an array.

To improve the performance of a linked list for accessing and searching elements, sorted linked lists can be augmented with ancillary structures. One such structure is known as a skip list. A skip list creates multiple layers of linked lists, or a hierarchy, each layer including some fraction of the number of the nodes of the original list. This makes it possible to find the places of significant elements in a list faster by trading off space for time. Skip lists can be thought of as pre-computing binary search nodes in a list, or as a sparse index. Using skip lists mitigates some of the performance deficiencies of linked lists compared to arrays, bringing down search time to O(log n) time, at the expense of using more space. 

Time complexity of a linked list

5.2.2 Linked list algorithm complexity

Sorting and searching linked lists may not be as common as they are for arrays, but can still be done. 

Sorting a linked list allows you to easily change the position of an element in the list, simply by re-assigning the links to its containing node. Compare this to changing the position of an element in an array, which generally means copying and moving multiple other elements, using extra temporary space.

However, to access a random element takes far longer in a linked list than in an array. Mergesort is preferred over Quicksort with a linked list, as Quicksort has a heavier reliance on random access to elements, which is slower in linked lists than arrays.

Search algorithms operating naively on linked lists generally take longer than searching in an array, due to the lack of inherent random access required by algorithms such as binary search. However, these algorithms can be sped up to similar time orders of complexity by using techniques such as skip lists, and using fast and slow pointers.

6. Mock interviews for software engineers

Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only linked lists but also the rest of the relevant data structures. Check out our guides for questions, explanations and helpful cheat sheets.

Once you’re confident on all the topics, you’ll want to start practicing answering coding questions in an interview situation.

One way of doing this is by practicing out loud, which is a very underrated way of preparing. However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your interview skills.

That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.

Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.

 

Related articles:

Facebook production engineer interview
Software engineeringJul 20, 2022
Meta production engineer interview (questions, prep, and process)
Complete guide to Meta (formerly Facebook) production engineer interviews. Learn the interview process, practice with example questions, and learn key preparation tips.
Read more
Amazon behavioral interview
Software engineeringApr 23, 2024
Amazon Behavioral Interview Questions (+ answers, method)
Everything you need to know about Amazon behavioral interviews and leadership principles. Learn what to expect and how to answer, with insights from ex-Amazon interviewers. Practice with over 60 example questions, see example answers and find links to high-quality prep resources.
Read more
Google interview questions
Software engineeringMay 11, 2023
Google interview questions and answers (SWE, PM, etc)
Complete guide to Google interview questions for software engineers, engineering managers, product managers, TPMs and data scientists. Contains 25 example answers, 200+ real Google questions, and links to detailed guides on how to answer.
Read more
Graph interview questions and cheatsheet
Software engineeringSep 27, 2021
50+ graph interview questions and cheat sheet
50+ graph interview questions, all with links to high-quality solutions, plus a graph refresher and cheat sheet. Part 6 of our coding prep series to help you ace your software engineer interview.
Read more
database system design interview
Software engineeringFeb 02, 2021
Databases: system design interview concepts (2 of 9)
This guide covers databases, how they work and what you should consider when using them in a system. This is the 2nd of 9 foundational system design interview concepts that we're covering on our blog.
Read more
Google Site reliability engineer interview
Software engineeringJun 06, 2023
Google Site Reliability Engineer (SRE) Interview (questions, process, prep)
Complete guide to the Google site reliability engineer interview. Understand the interview process, learn what questions to expect and see how to prepare. Plus, links to more great free SRE resources.
Read more
sharding system design interview
Software engineeringFeb 14, 2023
Sharding: system design interview concepts (7 of 9)
This guide defines sharding, how it works, and when you should use it in a system. This is the 7th of 9 foundational system design interview concepts that we're covering on our blog.
Read more
Airbnb software engineer interview
Software engineeringSep 22, 2020
Airbnb software engineer interview (questions and process)
This is a complete guide to Airbnb software engineer (SWE) interviews. It covers Airbnb's interview process, practice questions, and preparation tips.
Read more