[数据结构与算法]【LeetCode - 链表】

链表熟练，知道常规技巧后，应该属于比较固定思维的题目，难度不大

1. 合并链表
2. 判断链表是否成环，返回环的起点
3. 返回相交链表的节点

链表的节点值相等，是不能说明链表节点相等的

eq 没有打印出来，说明链表中第一个节点和第三个节点是不相等的

合并链表
合并链表直接用vector数据结构就行

class Solution {
public:
    ListNode* reverseList(ListNode* head) { // 返回链表的实质是返回指针
        vector<int> vec;
        while (head != nullptr) {    // 这里应该是直接判断节点是否为空while (head->val != NULL)
            vec.push_back(head->val);
            head = head->next;
        }
        reverse(vec.begin(), vec.end());
        ListNode* preNode = new ListNode(1);
        ListNode* res = preNode;
        for (int val : vec) {   // 取出vec中的值，直接一个：，即可取出
            ListNode* tempListNode = new ListNode(val);   // new一个节点的时候，前面需要加上*
            preNode->next = tempListNode;
            preNode = preNode->next;
        }
        return res->next;
    }
};

判断链表是否成环，环的起点
添加链接描述

1. 用set数据结构简单明了

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

2. 用快慢指针，用到了数学推到
   快慢指针节点相遇，将其中任意指针指向开头，两个指针一步走

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (slow != nullptr && fast != nullptr) {
            if (slow->next == nullptr) {
                return nullptr;
            }
            if (fast->next == nullptr || fast->next->next == nullptr) {
                return 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;
    }
};

相交链表的节点
a，b节点遍历，a遍历到末尾则指向b，b遍历到末尾则指向a，继续遍历当两个节点相等直接返回
添加链接描述

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖