刷题 链表

面试经典150题 - 链表

141. 环形链表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};

142. 环形链表 II

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            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;
    }
};

2. 两数相加 - 虚拟头节点 + 加法进位

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy_head = new ListNode(0);
        ListNode* cur = dummy_head, *cur_1 = l1, *cur_2 = l2;
        int sum = 0, carry = 0;
        while (cur_1 || cur_2 || carry != 0) {
            sum = 0;
            if (cur_1) {
                sum += cur_1->val;
                cur_1 = cur_1->next;
            }
            if (cur_2) {
                sum += cur_2->val;
                cur_2 = cur_2->next;
            }
            sum += carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
        }
        ListNode* head = dummy_head->next;
        delete dummy_head;
        dummy_head = nullptr;
        return head;
    }
};

21. 合并两个有序链表 - 虚拟头节点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* node_1, ListNode* node_2) {
        ListNode* dummy_head = new ListNode();
        ListNode* cur = dummy_head;
        while (node_1 != nullptr && node_2 != nullptr) {
            if (node_1->val < node_2->val) {
                cur->next = node_1;
                node_1 = node_1->next;
            } else {
                cur->next = node_2;
                node_2 = node_2->next;
            }
            cur = cur->next;
        }
        cur->next = node_1 ? node_1 : node_2; // 直接连接剩余部分
        ListNode* head = dummy_head->next;
        delete dummy_head;
        dummy_head = nullptr;
        return head;
    }
};

138. 随机链表的复制 - 深拷贝 - 哈希表存储对应关系

class Solution {
public:
    // 本题相当于 对 链表进行深拷贝
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> copy_hash;
        Node* cur = head;
        // 先 根据节点的值 新建拷贝，并通过哈希表关联
        while (cur) {
            copy_hash[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        // 根据哈希表 将 拷贝节点 连接起来 (next, random)
        while (cur) {
            copy_hash[cur]->random = copy_hash[cur->random];
            copy_hash[cur]->next = copy_hash[cur->next];
            cur = cur->next;
        }
        return copy_hash[head];
    }
};