Linked List Basics

linked_list.cpp

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int val) {
        this->val = val;
        this->next = nullptr;
    }
};

void printLinkedList(ListNode *head)
{
    while (head != nullptr) {
        cout << head->val << "->";
        head = head->next;
    }
    cout << "null" << endl;   
}

/* Fast-Slow Pointers (快慢指针)
   1. 找到链表的中间节点（⚠️对于偶数个节点，应该明确“中间”的含义：例如6节点链表，第3、4个节点都可以理解为中点）
   2. 判断链表是否有环 + 找到有环链表的环起始节点 */
ListNode *findMiddle(ListNode *head)    // T[O(n)] S[O(1)]
{
    if (head == nullptr)
        return nullptr;
    
    ListNode *fast = head, *slow = head;              
    while (fast->next && fast->next->next) { // N1 -> N2 -> N3 -> N4 -> NULL (N2 is defined as middle)
        slow = slow->next;                   // while (fast && fast->next) {...} (N3 is defined as middle)
        fast = fast->next->next;
    }
    return slow;
}

/* 简单数学证明：快慢指针速度分别为2和1，环周长为c，(2 - 1) * t = c 一定有整数解 t = c
   同时证明慢指针一定不会套圈 */
bool hasCycle(ListNode *head)           // T[O(n)] S[O(1)]
{
    if (head == nullptr || head->next == nullptr)
        return false;
    
    ListNode *fast = head, *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }
    return false;
}

/* 简单数学证明可见：https://leetcode.com/problems/linked-list-cycle-ii/solution/ */
ListNode *detectCycle(ListNode *head)    // T[O(n)] S[O(1)]
{
    if (head == nullptr || head->next == nullptr)
        return nullptr;
    
    ListNode *fast = head, *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        } 
    }
        
    return nullptr;
}

/* Insert a node in a sorted list */
ListNode *insertNode(ListNode* head, int target)
{
    // target should be inserted at the beginning
    if (head == nullptr || target <= head->val) {
        ListNode *new_head = new ListNode(target);
        new_head->next = head;
        return new_head;
    }
    
    // target should be inserted into somewhere in the middle
    ListNode *prev = nullptr, *curr = head;
    while (curr) {
        if (curr->val < target) {
            // move forward
            prev = curr;
            curr = curr->next;
        } else {
            prev->next = new ListNode(target);
            prev->next->next = curr;
            return head;
        }
    }
    
    // target should be inserted in the end (curr -> NULL, prev -> last node)
    prev->next = new ListNode(target);
    return head;
}

/* Remove a node from a linked list */
ListNode *removeNode(ListNode *head, int target)
{
    ListNode *dummy = new ListNode(-1);
    dummy->next = head;
    
    ListNode *prev = dummy;
    while (head) {
        if (head->val == target) {
            prev->next = prev->next->next;
            break;
        }
        head = head->next;
        prev = prev->next;
    }
    
    ListNode *new_head = dummy->next;
    delete dummy;
    return new_head;
}

/* Merge two sorted linked lists */
ListNode *mergeSortedList(ListNode *head1, ListNode *head2)
{
    ListNode *dummy = new ListNode(-1);
    ListNode *tail = dummy;
    
    while (head1 && head2) {
        if (head1->val <= head2->val) {
            tail->next = head1;
            head1 = head1->next;
        } else {
            tail->next = head2;
            head2 = head2->next;
        }
        tail = tail->next;
    }
    
    // there is ONLY one linked list left with unlinked nodes
    if (head1) tail->next = head1;
    if (head2) tail->next = head2;
    
    ListNode *new_head = dummy->next;
    delete dummy;
    return new_head;
}

/* Partition a linked list (keep the original relative order) */
ListNode *partitionList(ListNode *head, int pivot)
{
    ListNode *dummy1 = new ListNode(-1);
    ListNode *dummy2 = new ListNode(-1);
    
    ListNode *small = dummy1;
    ListNode *large = dummy2;
    while (head) {
        if (head->val <= pivot) {
            small->next = head;
            head = head->next;
            small = small->next;
        } else {
            large->next = head;
            head = head->next;
            large = large->next;
        }
    }
    
    ListNode *new_head = dummy1->next;
    // link the smaller and larger part
    small->next = dummy2->next;
    large->next = nullptr;  // make sure the last node is linked to NULL
    delete dummy1;
    delete dummy2;
    return new_head;
}

/* Reverse a linked list */
// iterative: T[O(n)], S[O(1)]
ListNode *reverseList(ListNode *head)
{
    ListNode *curr = head, *prev = nullptr;
    while (curr) {
        ListNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
        
    return prev;
}

// recursive: T[O(n)], S[O(n)]
ListNode* reverseList(ListNode* head)
{
    if (head == nullptr || head->next == nullptr)
        return head;

    ListNode *new_head = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return new_head;
}