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;
    }
};