List Theory

A list is a collection of items stored at non-contiguous memory locations. The list elements can be accessed using an index.

1
2
3
4
5
6
7

struct Node {
    int data;
    Node* next;
    Node(int x) data(x), next(NULL) {}
};

Operations

  • Insertion:
  • Deletion:

Note

  • A dummy head can simplify the logic and make the code more robust
  • Deleting the memory for removed nodes and setting the pointers to NULL is a good practice
  • while(i--) will execute i times, while while(--i) will execute i-1 times

practice
Leetcode 707 - Design Linked List

Remove Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

idea

Note

  • we need to delete the skipped node (cpp)
  • we need to consider the case when the first node should be removed
    1. move the head pointer back until it’s value is not targeted value
    2. create a dummy node and then we can treat the head as a normal node

practice
LeetCode 203 - Remove Linked List Elements

Complex Operations

Note

  • Use a dummy head to treat the header as a normal node (remember to delete it in the end).
  • We can use a fast-slow pointer approach to form a pursuit problem, which is usually applied in cycle detection problems.
  • After forming a pursuit problem, we can solve the problem mathematically.
  • Moving two pointers at the same pace will maintain a constant gap, which is also useful.

practice
LeetCode 206 - Reverse Linked List
LeetCode 160 - Intersection of Two Linked Lists
LeetCode 19 - Remove Nth Node From End of List
LeetCode 142 - Linked List Cycle II