力扣刷题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;elsereturn 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 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。