面试经典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];}
};