Leetcode 刷题记录 07 —— 链表

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答。

01 相交链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {}
};

① int val是一个整数类型的成员变量，用于存储链表节点的数据值。

② ListNode *next 是一个指向 ListNode 类型的指针，用于保存下一个节点的地址。

③ ListNode(int x) : val(x), next(NULL) {}是一个构造函数，用于创建一个 ListNode 对象。

其中，val(x) 使用初始化列表的语法，将参数 x 的值赋给成员变量 val。nex (NULL) 将 next 指针初始化为 NULL。这表示初始化新节点时，它暂时不指向任何其他节点。

方法一：哈希集合

时间复杂度 O(m + n)，空间复杂度 O(m)

• 建立无序集合 visited，存储链表 A 中的元素情况
• 遍历链表 B，判断 visited.count(temp)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> visited;ListNode *temp;temp = headA;while(temp != nullptr){visited.insert(temp);temp = temp -> next;}temp = headB;while(temp != nullptr){if(visited.count(temp)) return temp;temp = temp -> next;}return nullptr;}
};

① nullptr 是一种专门用于指针的文字常量，用于表示空指针。

② NULL 通常在 C 和 C++ 中被定义为整数常量 0，这有时会导致歧义和一些不希望发生的类型转换问题。

#include <iostream>void func(int) {std::cout << "Integer version called" << std::endl;
}void func(char*) {std::cout << "Pointer version called" << std::endl;
}int main() {func(nullptr); // 这将会调用指针版本的函数，因为 nullptr 是指针类型return 0;
}

方法二：双指针

时间复杂度 O(m + n)，空间复杂度 O(1)

• 建立双指针 ListNode *pA 和 ListNode *pB ，指向头元素
• 遍历链表 A 和链表 B，判断 pA == nullptr 和 pB == nullptr，移动双指针，直到 pA == pB

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA == nullptr || headB == nullptr) return nullptr;ListNode *pA = headA;ListNode *pB = headB;while(pA != pB){if(pA == nullptr) pA = headB;else pA = pA -> next;if(pB == nullptr) pB = headA;else pB = pB -> next;}return pA;}
};

02 反转链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {}
};

方法一：双指针

时间复杂度 O(n)，空间复杂度 O(1)

• 建立双指针 *prev 和 *curr，分别指向前一个结点和当前结点
• 遍历链表，判断 curr != nullptr ，执行 curr -> next = prev;

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *prev = nullptr;ListNode *curr = head;while(curr != nullptr){ListNode *next = curr -> next;curr -> next = prev;prev = curr;curr = next;}return prev;}
};

方法二：递归

时间复杂度 O(n)，空间复杂度 O(1)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head || !head->next) return head;ListNode *newNode = reverseList(head->next); //⭐head->next->next = head;head->next = nullptr;return newNode;}
};

03 回文链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {}
};

方法一：数组 + 双指针

时间复杂度 O(n)，空间复杂度 O(n)

• 建立数组 vals，存储链表中的元素情况
• 遍历数组，判断 vals[i] != vals[j]

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {vector<int> vals;while(head != nullptr){vals.push_back(head -> val);head = head -> next;}for(int i=0, j=(int)vals.size()-1; i<j; ++i, --j){if(vals[i] != vals[j]) return false;}return true;}
};

为什么没有判断 if(head == nullptr) return true; ？

可以在函数开始时加入 if (head == nullptr) return true;作为显式的情况处理以表明逻辑上的完整性，不过，代码中两段循环的跳过可以隐式的处理 head == nullptr 的情况并直接 return true。

方法二：递归 + 双指针

时间复杂度 O(n)，空间复杂度 O(n)

• 建立前端指针 frontNode 和后端指针 currentNode
• 遍历数组，判断 frontNode -> val != currentNode -> val

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {ListNode* frontNode; //前端指针
public:bool recursivelyCheck(ListNode* currentNode){ //后端指针if(currentNode){if(!recursivelyCheck(currentNode -> next)) return false; //递归式⭐if(frontNode -> val != currentNode -> val) return false;frontNode = frontNode -> next;}return true;}bool isPalindrome(ListNode* head) {frontNode = head;return recursivelyCheck(head);}
};

① recursively 递归地、reverse 逆转、palindrome / ˈpælɪndroʊm / 回文

② 在运行递归函数时，计算机需要在进入被调用函数之前跟踪它在当前函数中的位置（以及任何局部变量的值），通过运行时存放在堆栈中来实现（堆栈帧）。

③ 为什么没有判断 if(head == nullptr) return true; ？

当 head 为 nullptr 时，recursivelyCheck 函数会立即识别到，并返回 true，这相当于隐式地处理了空链表的特殊情况。

方法三：快慢指针 + 反转链表

时间复杂度 O(n)，空间复杂度 O(1)

• 找结点：建立快慢指针 fast 和 slow，找到链表前半部分的结束点
• 翻链表：利用反转链表，建立 prev 和 curr，找到链表后半部分的结束点
• 遍历链表，判断 p1->val != p2->val
• 注：需要在最后将反转的部分链表反转回来

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public://找结点ListNode* findNode(ListNode* head){ListNode* fast = head;ListNode* slow = head;while(fast->next != nullptr && fast->next->next != nullptr){fast = fast->next->next;slow = slow->next;}return slow;}//翻链表ListNode* reverseList(ListNode* head){ListNode* prev = nullptr;ListNode* curr = head;while(curr != nullptr){ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}bool isPalindrome(ListNode* head) {if(head == nullptr) return true;ListNode* firstHalfEnd = findNode(head); //找结点ListNode* secondHalfStart = reverseList(firstHalfEnd->next); //翻链表ListNode* p1 = head;ListNode* p2 = secondHalfStart;bool result = true;while(result && p2 != nullptr){if(p1->val != p2->val) result = false;p1 = p1->next;p2 = p2->next;}firstHalfEnd->next = reverseList(secondHalfStart); //神来之笔，翻回链表return result;}
};

为什么需要判断 if(head == nullptr) return true; ？

如果没有这个判断，接下来代码中任何对链表操作（比如访问节点值或找到中间节点）都会试图访问一个空指针，从而导致运行时错误（segmentation fault）。另外，快速返回的策略使得对特殊情况的处理更高效。

04 环形链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {}
};

方法一：哈希表

时间复杂度 O(n)，空间复杂度 O(n)

• 建立无序集合 visited，存储已经访问的元素
• 遍历链表，判断 visited.count(head)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {unordered_set<ListNode*> visited;while(head != nullptr){if(visited.count(head)) return true;visited.insert(head);head = head->next;}return false;}
};

方法二：快慢指针

「Floyd 判圈算法」（龟兔赛跑算法）

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

• 建立快慢指针 fast 和 slow，假装乌龟和兔子
• 遍历链表，判断 slow != fast
• 注：if(fast == nullptr || fast->next == nullptr) return false;

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if(head == nullptr || head->next == nullptr) return false;ListNode* slow = head;ListNode* fast = head->next;while(slow != fast){if(fast == nullptr || fast->next == nullptr) return false;fast = fast->next->next;slow = slow->next;}return true;}
};

05 环形链表Ⅱ

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {}
};

时间复杂度 O(n)，空间复杂度 O(n)

• 建立无序集合 visited，存储已经访问的元素
• 遍历链表，判断 visited.count(head)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {unordered_set<ListNode*> visited;while(head != nullptr){if(visited.count(head)) return head;visited.insert(head);head = head->next;}return nullptr;}
};

方法二：快慢指针

• 建立快慢指针 fast 和 slow，假装乌龟和兔子
• 遍历链表，判断 slow != fast，成立，建立额外指针 pear，假装小熊
• 小熊从原点出发，它和乌龟会在入环点相遇

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* slow = head;ListNode* fast = head;while(fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;//改动部分if(fast == slow){ListNode* pear = head;while(pear != slow){pear = pear->next;slow = slow->next;}return pear;}}return nullptr;}
};