Linked Lists

Lecture Slides

A Linked List is a data structure that contains a sequence of nodes such that each node contains an object and a reference to the next node in the list, the first node is refered as the head and the last is referred to as the tail. There are two difference linked list:

• Singly Linked List
• Doubly Linked List

Must Know:

How to implement a linked list

Linked List Basic Operations

• Insert O(n)
  • When can this operation be fast?
• Delete a node O(n)
  • When can this operation be fast?
• Search for a node O(n)

Linked List Recursions

Explanation

• Finding the Length of a list
• Searching for a value
• Print the list
• Inserting an Item into a sorted list
• Deleting an item from a list
• Appending two lists
• Zipping two lists
• Merging two sorted lists
• Reversing a List

Tricks

Dummy Head

• EPI 8.1 Merge Two Sorted Lists
  • Question: How to merge two sorted arrays?

Runner Method

• Distance Runner

• Slow and Fast

  • EPI 8.3 Test For Cyclicity
  • CCTI 2.3 Delete the Middle Node

##Problem Set

Elements of Programming Interviews 2015

• 8.1 Merge Two Sorted Lists
• 8.2 Reverse A Single Sublist
• 8.3 Test For Cyclicity
• 8.4 Test For Overlapping Lists No Cycles
• 8.5 Test For Overlapping Lists Might Have Cycles
• 8.6 Delete A Node From A Singly LinkedList
• 8.7 Remove the Kth Last Element From a List
• 8.8 Remove Duplicates from a Sorted List
• 8.9 Implement Cycle Right Shift For Singly LinkedList
• 8.10 Implement Even Odd Merge
• 8.11 Test Whether a Singly LinkedList is Palindromic
• 8.12 Implement List Pivoting
• 8.13 Add List-based Integers

Cracking the code interviews 6e

• 2.1 Remove Duplicates From a Unsorted LinkedList
• 2.3 Delete the Middle Node

Leetcode

• 24. Swap Nodes in Pairs
• 203. Remove Linked List Elements
• 143. Reorder List
• 147. Insertion Sort List
• 148. Sort List

GeeksforGeeks

• Merge Sort for Linkedlist

Others

Hard