Linked list patterns for LeetCode and coding interviews

When working with linked lists, we need to remember several basic patterns.

Linked List Node Structure

A linked list node typically contains a value and a pointer to the next node.
For a singly linked list it is:

struct ListNode {
    int val;
    ListNode* next;

    ListNode(int x) : val(x), next(nullptr) {}
};

Visually:

head
 ↓
[1] → [2] → [3] → nullptr

Linked List Traversal

Typically, we traverse the linked list from the head to the tail.

ListNode* current = head;

while (current != nullptr) {
    cout << current->val << '\n';
    current = current->next;
}

Remember:

current = head

while (current != nullptr) {
    use current
    current = current->next
}

Visually:

current
 ↓
[1] → [2] → [3] → nullptr
      current
       ↓
[1] → [2] → [3] → nullptr
            current
             ↓
[1] → [2] → [3] → nullptr

Searching for an element

Searching for target. If found, return a pointer to the node, not just its value.

ListNode* find(ListNode* head, int target) 
{
  ListNode* current = head;

  while(current != nullptr)
  {
    if(current->val == target) 
      return current;

    current = current->next;
  }

  return nullptr;
}

Visually:

current
 ↓
[1] → [2] → [3] → nullptr
       ↑
    target = 2

Inserting a Node at the end

Find the last node, because we need to stop there.

void pushBack(ListNode*& head, int value)
{
  ListNode* node = new ListNode(value);

  if(head == nullptr)
  {
    head = node;
    return;
  }

  ListNode* current = head;

  while(current->next != nullptr)
  {
    current = current->next;
  }

  current->next = node;
}

Visually:
First:

current
 ↓
[1] → [2] → [3] → nullptr
             ↑
      current->next == nullptr

Second:

current->next = node;

[1] → [2] → [3] → [4] → nullptr

Inserting a Node at the head

void pushFront(ListNode*& head, int value)
{
  ListNode* node = new ListNode(value);

  node->next = head;
  head = node;
}

Visually
Before:

head
 ↓
[2] → [3] → nullptr

After:

node->next = head;

[1] ─────┐
         ↓
        [2] → [3]

head = node;

head
 ↓
[1] → [2] → [3] → nullptr

Core Linked List patterns

TRAVERSE

current = head

while(current)
{
  ...
  current = current->next;
}

SEARCH

while(current)
{
  if(current->val == target)
    return current;

  current = current->next;
}

FIND LAST

while(current->next)
{
  current = current->next;
}

INSERT FRONT

node->next = head;
head = node;

Need to know

Solving almost any linked-list problem starts with understanding the difference between current and current->next

current - current node
current->next - pointer to the next node

And that's exactly why:

while(current) - traverses the entire linked list and stops when current == nullptr
while(current->next) - stops at the last node