Topic 05 of 15
Linked List
A toy train.
A linked list is a toy train. Each car holds a value and a hook to the next car. You cannot jump to car number 5; you have to walk from the engine. In return, adding or removing a car in the middle is just changing two hooks.
What you will be able to do
Pointer rewiringFast and slow pointersDummy head nodesMerging listsCycle detection
0/36
Meet the linked list
01 / 04
Four cars. Each one points to the next. The last one points to null, which means the end.
- looking now
- seen
- answer
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Write a Program to reverse the Linked List (Both Iterative and recursive)Turn a train of cars around so the last car becomes the first, by flipping each coupling one at a time.Pointer flipping
- 02Reverse a Linked List in group of Given SizeCut a chain of boxes into groups of k, turn each full group around, and hook the groups back together in the same order.Pointer flippingMust do
- 03Write a program to Detect loop in a linked listFind out if a chain of boxes secretly bends back into a circle, by sending a slow runner and a fast runner and seeing if they ever meet.Fast and slow pointers
- 04Write a program to Delete loop in a linked listFix a chain of boxes that bends back into a circle by finding the box where the circle starts and cutting the arrow that leads back to it.Fast and slow pointers
- 05Find the starting point of the loopA chain of boxes curls back into a loop somewhere, and you must find the exact box where the loop begins.Fast and slow pointers
- 06Remove Duplicates in a sorted Linked ListIn a chain of boxes already in order, copies always sit next to each other, so walk once and skip every box that matches the one before it.Single pointer skip
- 07Remove Duplicates in a Un-sorted Linked ListWalk a jumbled chain of boxes once, remember every number in a bag, and unhook any box whose number is already in the bag.Hash set lookup
- 08Write a Program to Move the last element to Front in a Linked ListTake the last box of a chain and make it the new first box, by walking with two fingers one box apart and changing three arrows.Trailing pointer
- 09Add 1 to a number represented as a Linked ListA number is written one digit per box in a chain, and you must add 1 to it, carrying over the 9s like an odometer.Last non 9 pointer
- 10Add two numbers represented by linked listsTwo numbers are written one digit per box, biggest digit first, and you add them the way you add on paper, carrying when a column passes 9.Reverse and carry
- 11Intersection of two Sorted Linked ListTwo sorted chains of numbered boxes: build a brand new chain holding only the numbers that appear in both.Two pointers
- 12Intersection Point of two Linked ListsTwo chains start apart and join into one shared tail like the letter Y, and you must find the box where they join.Two pointers that switch lists
- 13Merge Sort For Linked listsSort a chain of boxes by cutting it in half again and again until every piece is one box, then zipping sorted pieces back together.Divide and conquerMust do
- 14Quicksort for Linked ListsSort a chain of boxes with quicksort: pick one number as the judge, send every box to a smaller, same or bigger pile, sort the piles, and hook them back together.Divide and conquerMust do
- 15Find the middle Element of a linked listFind the box in the middle of a chain in one walk, by sending one runner twice as fast as the other.Fast and slow pointers
- 16Check if a linked list is a circular linked listDecide if a chain of boxes is a ring, where the last box holds hands with the very first box again.Fast and slow pointers
- 17Split a Circular linked list into two halvesCut a ring of boxes into two smaller rings of equal size by sending a fast runner and a slow runner around it once.Fast and slow pointers
- 18Write a Program to check whether the Singly Linked list is a palindrome or notCheck if a one way chain reads the same from both ends by finding its middle, turning the back half around, and comparing the halves box by box.Fast and slow pointers
- 19Deletion from a Circular Linked ListTake one kid out of a ring of kids holding hands, and make the two kids beside them hold hands so the ring stays closed.Previous pointer walk
- 20Reverse a Doubly Linked listTurn a two way chain around by letting every box swap its front arrow and its back arrow, like a line of kids doing an about face.Pointer swapping
- 21Find pairs with a given sum in a DLLIn a sorted chain where every box can step forward and back, find every pair of boxes whose numbers add up to a target.Two pointers
- 22Count triplets in a sorted DLL whose sum is equal to given value XCount the groups of three boxes in a sorted two way chain whose numbers add up to x, by fixing one box and squeezing the rest from both ends.Two pointers
- 23Sort a k sorted Doubly Linked listSort a two way chain where every box is at most k places from where it belongs, by keeping only the next k + 1 boxes in a small pile that always hands you the smallest.Heap of size kMust do
- 24Rotate Doubly Linked list by N nodesMove the first N boxes of a two way chain to its end by joining the chain into a ring and cutting it at the right spot.Make a ring, then cut
- 25Rotate a Doubly Linked list in group of Given SizeCut a two way chain into groups of k, turn each group around (the last short group too), and hook every group to its neighbors in both directions.Pointer flippingMust do
- 26Can we reverse a linked list in less than O(n)Can a chain of boxes be turned around faster than touching every box? Not a one way chain, but a two way chain can start reading from the other end instead.Direction flag
- 27Why Quicksort is preferred for Arrays and Merge Sort for LinkedListsQuicksort loves rows of boxes you can jump around in, merge sort loves chains you can only walk along, and this page shows why.Divide and conquer
- 28Flatten a Linked ListA row of boxes where each box has its own sorted column hanging below it must become one sorted column.Merge sorted lists
- 29Sort a LL of 0s, 1s and 2sSort a chain that only holds 0s, 1s and 2s by sending each box to one of three little lines and then joining the lines in order.Split into lists and join
- 30Clone a linked list with next and random pointerMake a perfect twin of a chain where every box also has a second arrow pointing anywhere, so the twin boxes point at twin boxes and never at the old ones.Interleave copies
- 31Merge K sorted Linked listSeveral sorted chains must become one sorted chain, by always picking the smallest box from the fronts of all the chains.Heap of size k
- 32Multiply 2 no. represented by LLTwo huge numbers are written one digit per box, and you must give back their product cut down to a fixed size by a remainder, without ever holding the giant numbers.Modular arithmetic
- 33Delete nodes which have a greater value on right sideRemove every box that has a bigger number somewhere after it in the chain, so only the leaders who can see over everyone behind them are left.Reverse and running max
- 34Segregate even and odd nodes in a Linked ListMove every even box of a chain to the front and every odd box to the back, keeping each group in its old order, by building two little lines and joining them.Split into lists and join
- 35Program for nth node from the end of a Linked ListFind the box that sits n places from the end of a chain, by sending one finger n steps ahead and then walking both fingers together.Two pointers
- 36Find the first non-repeating character from a stream of charactersLetters arrive one at a time, and after each one you must say which letter that has shown up only once arrived first.Doubly linked list plus hash map