力扣刷题DAY2（链表/简单）

一、回文链表

回文链表

方法一：双指针 /** * 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) { vals.emplace_back(head->val); head = head->next; } for (int i = 0, j = vals.size() - 1; i < j; i++, j--) { if (vals[i] != vals[j]) return false; } return true; } };

思路：把链表的值存入一个vector，然后首尾双指针判断值是否相等。

复杂度分析

时间复杂度：O(n)，其中 n 指的是链表的元素个数。空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

查漏补缺：

vals.emplace_back(head->val);

作用：将 head->val 的值直接构造到 vals 的末尾。

for (int i = 0, j = vals.size() - 1; i < j; i++, j--) { if (vals[i] != vals[j]) return false; }

作用：计算 vals 的size 。

方法二：快慢指针

快慢指针参考 详解双指针算法（一）之快慢指针

/** * 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* midNode(ListNode* head) { ListNode* fast = head; ListNode* slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } // 逆序 ListNode* reverse(ListNode* head) { ListNode* pre = nullptr; while (head) { ListNode* newnode = head -> next; head->next = pre; pre = head; head = newnode; } return pre; } bool isPalindrome(ListNode* head) { ListNode* mid = midNode(head); // 给后半段逆序 ListNode *head2 = reverse(mid); while (head2) { if (head->val != head2->val) { // 不是回文链表 return false; } head = head->next; head2 = head2->next; } return true; } };

复杂度分析

时间复杂度：O(n)，其中 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* reverse(ListNode* head) { ListNode* pre = nullptr; while (head) { ListNode* temp = head->next; head->next = pre; pre = head; head = temp; } return pre; } ListNode* midNode(ListNode* head) { ListNode* fast = head; ListNode* slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } void reorderList(ListNode* head) { ListNode* mid = midNode(head); ListNode* head2 = reverse(mid->next); ListNode* head1 = head; mid->next = nullptr; while (head2) { ListNode* beh1 = head1->next; ListNode* beh2 = head2->next; head1->next = head2; head2->next = beh1; head1 = beh1; head2 = beh2; } } };

易错点1：

必须要让mid是前半部分的最后一个节点，mid->next是后半部分的第一个节点才行。

因为重排逻辑决定了必须要是123  45才能正确重排。

 易错点2：

由于mid是前半部分的最后一个节点，就必须显示规定一个 mid->next=nullptr，这样才能保证前后两段完全断开，保证重排逻辑正确。

二、环形链表

环形链表

方法一：快慢指针 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; } slow = slow->next; fast = fast->next->next; } return true; } };

复杂度分析

时间复杂度：O(N)，其中 N 是链表中的节点数。空间复杂度：O(1)。我们只使用了两个指针的额外空间。

类似题目：

快乐数

class Solution { public: int calcu(int n) { int res = 0; while (n) { res += (n % 10) * (n % 10); n /= 10; } return res; } bool isHappy(int n) { int slow = n; int fast = calcu(n); while (slow != fast) { slow = calcu(slow); fast = calcu(calcu(fast)); if (fast == 1) return true; } if (fast != 1) return false; else return true; } };

 疑点解析1：

会不会陷入无休止循环？不会。

 疑点解析2：

如果fast==slow!=1是否还要继续判断？不用。

因为二者相等时，说明slow已经进入了循环，不可能再出现1的情况了。

方法二：哈希表 /** * 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; ListNode *x=head; while(x){ if(visited.count(x)) return true; visited.insert(x); x=x->next; } return false; } };

思路：使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

复杂度分析

时间复杂度：O(N)，其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。空间复杂度：O(N)，其中 N 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。