hot100链表（1）

第一题：160. 相交链表 - 力扣（LeetCode）

方法：假设公共部分长度为z，A的长度为a+z，B的长度为b+z.当pa移动到了尾部，就让它为headB；当pb移动到了尾部，就让它是headA，然后继续往后移动。这样只要链表相交就一定会相遇，因为两个指针移动的长度都是a+b+z.

举个例子，A先跑200m，再跑600m，再跑400m。B先跑400m，再跑600m，再跑200m。只要AB二人速度一样，总会相遇。

先看一个错误示范：

/*** 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;if (pb == nullptr) pb = headA;pa = pa->next;pb = pb->next;}return pa;}
};

错因：先赋值再移动。以pa为例子。pa为nullptr时，将headB赋值给它。但接着又执行pa=pa->next.如果交点是某个链表的头节点，那就有可能错过。

正确做法应该是先判断究竟是该移动还是该赋值：

/*** 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){pa = (pa == nullptr ? headB : pa->next);pb = (pb == nullptr ? headA : pb->next);}return pa;}
};

第二题：反转链表206. 反转链表 - 力扣（LeetCode）

法一：双指针迭代

class Solution
{
public:ListNode* reverseList(ListNode* head){if (head == nullptr || head->next == nullptr) return head;ListNode* prev = nullptr;ListNode* curr = head;while (curr){ListNode* temp = curr->next;curr->next = prev;prev = curr;curr = temp;}return prev;}
};

法二：双指针递归？不知道这么叫是否准确，但是和法一差不多。一对一对往后推而已。

class Solution
{
public:ListNode* r(ListNode* prev, ListNode* curr){if (curr == nullptr) return prev;ListNode* temp = curr->next;curr->next = prev;return r(curr, temp);}ListNode* reverseList(ListNode* head){return r(nullptr,head);}
};

法三：递归

class Solution
{
public:ListNode* reverseList(ListNode* head){if (head == nullptr || head->next == nullptr) return head;ListNode* curr = reverseList(head->next);//cur为最后一个节点//此时head为倒数第二个节点head->next->next = head;head->next = nullptr;//避免循环//开始往前归return curr;}
};

第三题：234. 回文链表 - 力扣（LeetCode）

法一：最直接的方法，用一个数组存储链表节点的值，用双指针判断是否回文。

class Solution
{
public:bool check(vector<int>& vec){int n = vec.size();int left = 0, right = n - 1;while (left <= right){if (vec[left] != vec[right]) return false;left++, right--;}return true;}bool isPalindrome(ListNode* head){ListNode* curr = head;vector<int>vec;while (curr){vec.push_back(curr->val);curr = curr->next;}return check(vec);}
};

法二：找中点，反转后半部分。用快慢指针找中点。

长度为偶数：

设原链表为：1-> 2 -> 2 -> 1

处理后：1 -> 2 -> 2 <- 1

长度为奇数：

设原链表为：1 -> 3 -> 5 -> 3 -> 1

处理后：1 -> 3 -> 5 <- 3 <- 1

所以while循环的条件是head2不为nullptr

class Solution
{
public:ListNode* find_middle(ListNode* head){ListNode* slow = head, * fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reverseList(ListNode* head){if (head == nullptr || head->next == nullptr) return head;ListNode* prev = nullptr, * curr = head;while (curr) {ListNode* temp = curr->next;curr->next = prev;prev = curr;curr = temp;}return prev;}bool isPalindrome(ListNode* head){ListNode* mid = find_middle(head);ListNode* head2 = reverseList(mid);while (head2){if (head->val != head2->val) return false;head = head->next;head2 = head2->next;}return true;}
};