Must-Do LinkedList Problems on Leetcode

Image for post
Image for post

Notes

Adding a dummy node at the head and/or tail might help to handle many edge cases where operations have to be performed at the head or the tail. The presence of dummy nodes essentially ensures that operations will never have been done on the head or the tail, thereby removing a lot of headache in writing conditional checks to deal with null pointers. Be sure to remember to remove them at the end of the operation.

Sometimes linked lists problem can be solved without additional storage. Try to borrow ideas from reverse a linked list problem.

For deletion in linked lists, you can either modify the node values or change the node pointers. You might need to keep a reference to the previous element.

For partitioning linked lists, create two separate linked lists and join them back together.

Linked lists problems share similarity with array problems, think about how you would do it for an array and try to apply it to a linked list.

Two pointer approaches are also common for linked lists. For example:

  • Getting the kth from last node — Have two pointers, where one is k nodes ahead of the other. When the node ahead reaches the end, the other node is k nodes behind
  • Detecting cycles — Have two pointers, where one pointer increments twice as much as the other, if the two pointers meet, means that there is a cycle
  • Getting the middle node — Have two pointers, where one pointer increments twice as much as the other. When the faster node reaches the end of the list, the slower node will be at the middle

Common Routines

  • Counting the number of nodes in the linked list
  • Reversing a linked list in-place
  • Finding the middle node of the linked list using fast/slow pointers
  • Merging two lists together

Corner cases

  • Two nodes
  • A linked list has a cycle. Tip: Clarify with the interviewer whether there can be a cycle in the list. Usually, the answer is no

Recommended LeetCode questions

Written by

Software Engineer @Vedantu, Former Intern @Hackerrank, GSoC @Wikimedia, Former Intern @Vedantu, Codeforces(Expert)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store