力扣hot100【链表】

160.相交链表

题目
我的思路：两个链表一长一短，先把长的提前遍历使两个链表的长度相等，然后同时遍历，如果遍历的节点相等时说明相交，否则不相交。

/*** 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) {ListNode* p=headA;ListNode* q=headB;int countA=0,countB=0;while(p->next){countA++;p=p->next;}while(q->next){countB++;q=q->next;}int differ=abs(countA-countB);p=headA;q=headB;while(differ--){if(countA>countB){p=p->next;}else {q=q->next;}}while(p&&q){if(p==q)return p;p=p->next;q=q->next;}return NULL;}
};

官方：
方法一：哈希集合
把A的先放到哈希表内，然后遍历B，看B的节点是否有在A中的，如果有说明是交点。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> visited;ListNode *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;}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/811625/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

反思：查找交集的题目可以联想到哈希表。
方法二：双指针

142.环形链表2

题目
方法一：哈希

/*** 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;ListNode*p=head;while(p){if(!visited.count(p)){ visited.insert(p);}else return p;p=p->next;}return NULL;}
};

方法2：快慢指针
思路：公式推导（根据链条长度和快的是慢的两倍关系，推导环内长度与环外长度的倍数关系），再找快慢指针先相遇的地方，根据公式长度倍数关系，设置第三个指针，然后第三个指针与慢指针同时遍历，直到相遇的地方就是环的入口。
注意：fast指针的空的时候就是链表内无环。

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *slow = head, *fast = head;while (fast != nullptr) {slow = slow->next;if (fast->next == nullptr) {return nullptr;}fast = fast->next->next;if (fast == slow) {ListNode *ptr = head;while (ptr != slow) {ptr = ptr->next;slow = slow->next;}return ptr;}}return nullptr;}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/linked-list-cycle-ii/solutions/441131/huan-xing-lian-biao-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

24. 两两交换链表中的节点

题目
我的思路：双指针交换，卡的点：边界最后的交换，以及head==NULL时，还有while先判断q不为空，然后再q->next不为空，不能只写while(q->next).

/*** 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* swapPairs(ListNode* head) {if(head==NULL||head->next==NULL) return head;ListNode* p=head,*q=p->next;while(q&&q->next){if(q&&p)swap(q->val,p->val);p=q->next;q=p->next;            }if(q){swap(q->val,p->val);}return head;}
};

官方写的：没看。。

19. 删除链表倒数第N个节点

我的思路，双指针，相差N但是卡了bug进行了边界处理，而且多了一个没必要的pre指针，其实不好，不通用，官方的双指针用了虚拟头节点。

/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode*p=head,*q=head,*pre=head;while(n--){q=q->next;}  if(q==NULL)//卡了边界值的bug{return head->next;}      while(q){pre=p;p=p->next;q=q->next;}pre->next=p->next;return head;}
};

官方：没看，三种方法。。。

2.两数相加

题目
错误的：误以为只能两个长度一样的链表可以相加，其实长度不同也可以相加，并且用到了reverse(str),std::istoi(str)，其实完全不必要，看题解!!!我的问题是经常用while循环好几次，题解都是一次做好多事情，一次结束了。
错误的思路：只觉得两个链表长度相等才可相加，没有解决进位的问题。
下面是错误的：

/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* p=l1,*q=l2;ListNode* k=new ListNode(0),*head=k;string s1,s2;int num1,num2,sum;while(p->next&&q->next){s1+=p->val;s2+=q->val;p=p->next;q=q->next;}reverse(s1.begin(),s1.end());reverse(s2.begin(),s2.end());num1=std::stoi(s1);num2=std::stoi(s2);sum=num1+num2;while(sum){int num=sum/10;sum=sum/10;ListNode* t=new ListNode(num);k->next=t;k=k->next;}return head;}
};

官方思路：
l1,l2链表节点逐个相加，并且考虑进位，是进到下一个节点去了，使用的尾插法，刚好最后的结果也是逆序。
sum=node1->val+node2->val;
carry进位：sum/10
长度不相等时：短的链表后面有若干个0

/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head=NULL,*tail=NULL;int carry=0;while(l1||l2){int n1=l1?l1->val:0;int n2=l2?l2->val:0;int sum=n1+n2+carry;if(!head){head=tail=new ListNode(sum%10);  //注意这里是%而不是/}else{tail->next=new ListNode(sum%10); //新节点的next为空tail=tail->next;}carry=sum/10;if(l1){l1=l1->next;}if(l2){l2=l2->next;}if(carry>0){tail->next=new ListNode(carry);}}return head;}  
};

148. 排序链表

题目
我的思路：用一个数组存储链表的数据，然后使用sort逆序，再次遍历链表替换成逆序的数据。

/*** 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* sortList(ListNode* head) {ListNode* p=head;vector<int> v;while(p){v.push_back(p->val);p=p->next;}sort(v.begin(),v.end());p=head;int i=0;while(p){p->val=v[i++];p=p->next;}return head;}
};

官方：
归并排序，待看。。。。

138.随机链表的复制

题目
自己的想法是弄到数组里，然后再用哈希表查询看random是第几个，但是感觉很麻烦，看了评论区的一个方法：牛！

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {if(head==NULL)return NULL;unordered_map<Node*,Node*> map;   Node* cur=head;while(cur){map.emplace(cur,new Node(cur->val));cur=cur->next;}cur=head;while(cur){map[cur]->next=map[cur->next];map[cur]->random=map[cur->random];cur=cur->next;}return map[head];}
};