Skip to content
Mighten's Blog

Type to search…

↑↓ to navigate
Esc

Linked List

This blog post provides a comprehensive guide and C++ implementations for five frequently used Linked List algorithms.

Algorithms 2 min read

Today, let’s talk about Linked List algorithms that are frequently used.

A Linked List is a data structure that stores data into a series of connected nodes, and thus it can be dynamically allocated. For each node, it contains 2 fields: the val that stores data, and the next that points to the next node.

In LeetCode, the Linked List is often defined below, using C++:

struct ListNode {
    int val;
    ListNode *next;
};

The content of this blog is shown below:

mindmap
root)Linked List(
        A1(Node Removal)
        A2(Inplace Reversal)
        A3(Merge)
        A4(Insertion Sort)
        A5(Two Pointer)

LeetCode 203: Remove Linked List 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.

ListNode* removeElements(ListNode* head, int val){
    ListNode newHead;
    ListNode  *pre = &newHead;
    newHead.next = head;


    while (pre->next != nullptr ) {
        ListNode *cur = pre->next;
        if (cur->val == val ) {
            pre->next = cur->next;
            delete cur;
        }else
            pre = pre->next;
    }
    return newHead.next;
}

LeetCode 206. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

ListNode* reverseList(ListNode* head) {
    ListNode *pre = nullptr, *cur = head;
    while (cur != nullptr ) {
        ListNode *next = cur->next;
        cur->next = pre;
        pre = cur, cur = next;
    }
    return pre;
}

LeetCode 21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode head;
    ListNode *pre = &head;


    while (list1 != nullptr && list2 != nullptr ) {
        if (list1->val < list2->val ) {
            pre->next = list1;
            list1 = list1->next;
        } else {
            pre->next = list2;
            list2 = list2->next;
        }
        pre = pre->next;
    }


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


    while (list2 != nullptr ) {
        pre->next = list2;
        pre = pre->next;
        list2 = list2->next;
    }
    pre->next = nullptr;
    return head.next;
}

LeetCode 147. Insertion Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head.

The steps of the insertion sort algorithm:

  1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
  3. It repeats until no input elements remain.
ListNode* insertionSortList(ListNode* head) {
    if (head == nullptr) return head;
    ListNode tmpHead;
    ListNode *cur = head, *pre = &tmpHead;


    while (cur != nullptr) {
        while (pre->next != nullptr && pre->next->val < cur->val)
            pre = pre->next;


        ListNode* next = cur->next;
        cur->next = pre->next;
        pre->next = cur;
        pre = &tmpHead;
        cur = next;
    }
    return tmpHead.next;
}

We often use fast and slow to solve Linked List problems in O(n)O(n)-time complexity.

LeetCode 876. Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

ListNode* middleNode(ListNode* head) {
    ListNode *fast = head, *slow = head;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

LeetCode 142. Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Do not modify the linked list.

ListNode *detectCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;


    // Judge if cycle exists
    while ( true ) {
        if (fast == nullptr || fast->next == nullptr )
            return nullptr;
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;  // Cycle detect
    }


    // yes there is a cycle, and find the entry of cycle
    ListNode *ptr = head;
    while (ptr != slow ) {
        ptr = ptr->next;
        slow = slow->next;
    }
    return ptr;
}