一.【Leetcode206】反转链表
1.链接
2.题目再现
3.解法：三指针法
1.定义三个指针n1 n2 n3，n1指向空，n2指向头节点，n3指向头节点的next；
2.注意：要先判断是否是空链表；
3.用n2遍历链表，n2为空时就跳出循环；
4.翻转链表，即n2->next=n1；
5.翻转下一个节点，即n1=n2；n2=n3；n3=n3->next；
6.注意：在n3=n3->next前要先判断n3是否为空，若为空就结束循环，否则可能会发生对空指针的解引用；
7.n1为反转后的头节点，返回n1。
动态演示：
三指针动态演示
代码：
1. struct ListNode* reverseList(struct ListNode* head) 2. { 3. if(head==NULL) 4. return NULL; 5. struct ListNode*n1=NULL; 6. struct ListNode*n2=head; 7. struct ListNode*n3=n2->next; 8. while(n2) 9. { 10. n2->next=n1; 11. n1=n2; 12. n2=n3; 13. if(n3==NULL) 14. break; 15. n3=n3->next; 16. } 17. return n1; 18. }
二.【Leetcode21】合并两个有序链表
1.链接
2.题目再现
3.三指针尾插法
思路：创建一个新的链表，分别遍历两个链表，小的就尾插到新链表，然后指针向后走一步，直到有一方为空时就结束循环；结束循环后，判断哪个链表不为空，把不为空的尾插到新链表中去。
1.定义指针cur1=list1，cur2=list2，建立新的链表newlist，和保存新链表尾节点的指针tail；
2.注意：在遍历前要先判断两链表是否为空，若一方为空，则直接返回另一方；
3.分表遍历两个链表，比较其值，小的尾插到新链表，并向后走一步（如果一样大，那么随便取哪一个都行）；
4.结束循环后，判断哪个链表不为空，尾插到新链表。
动态演示：
合并两个有序链表动态演示
代码：
1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 2. { 3. if(list1==NULL) 4. return list2; 5. if(list2==NULL) 6. return list1; 7. struct ListNode*newlist=(struct ListNode*)malloc(sizeof(struct ListNode)); 8. struct ListNode*cur1=list1; 9. struct ListNode*cur2=list2; 10. struct ListNode*tail=newlist; 11. //newlist->next=tail; 12. while(cur1&&cur2) 13. { 14. if(cur1->val<cur2->val) 15. { 16. tail->next=cur1; 17. tail=tail->next; 18. cur1=cur1->next; 19. } 20. else 21. { 22. tail->next=cur2; 23. tail=tail->next; 24. cur2=cur2->next; 25. } 26. } 27. if(cur1) 28. { 29. tail->next=cur1; 30. } 31. if(cur2) 32. { 33. tail->next=cur2; 34. } 35. struct ListNode*head=newlist->next; 36. free(newlist); 37. newlist=NULL; 38. return head; 39. 40. }
三.【Leetcode160】相交链表
1.链接
2.题目再现
3.解法
1.先分别遍历两个链表，记录下两个链表的长度；
2.如果两个链表尾节点的地址一样，则说明它们相交，否则不相交，（注意是地址不是值）；
3.求出两个链表长度的差gap；
4.先让长的链表走差距步gap，短的链表先不动；
5.然后两个链表同时走一步，比较每走一步时两个链表当前节点的地址，如果一样，则说明找到了它们相交的起始位置，返回。
动态演示：
相交链表动态演示
代码：
1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 2. { 3. struct ListNode*tailA=NULL; 4. struct ListNode*tailB=NULL; 5. int n1=0,n2=0; 6. struct ListNode*cur1=headA,*cur2=headB; 7. while(cur1) 8. { 9. n1++; 10. tailA=cur1; 11. cur1=cur1->next; 12. } 13. while(cur2) 14. { 15. n2++; 16. tailB=cur2; 17. cur2=cur2->next; 18. } 19. if(tailA!=tailB) 20. return NULL; 21. int gap=n1-n2; 22. if(gap<0) 23. gap=-gap; 24. struct ListNode*longlist=headA,*shortlist=headB; 25. if(n1<n2) 26. { 27. longlist=headB; 28. shortlist=headA; 29. } 30. while(gap--) 31. { 32. longlist=longlist->next; 33. } 34. while(longlist!=shortlist) 35. { 36. longlist=longlist->next; 37. shortlist=shortlist->next; 38. } 39. 40. return longlist; 41. }
四.链表的回文结构
1.链接
2.题目再现
3.解法
首先我们得知道什么是回文结构？
简单来说，回文结构不管是正着读还是倒着读，结果是一样的；
我们就可以利用这一点来解决这道题。
1.找到链表的中间节点；
2.逆置链表中间节点以后的部分，rmid 为后半部分逆置后的第一个节点；
3.头指针 head 和 rmid 同时向后遍历，若 head 的值不等于 rmid 的值，则不是回文结构，返回 false ，循环结束后则是回文结构，返回 true 。
动态演示：
回文链表动态演示
代码：
1. struct ListNode* middleNode(struct ListNode* head) //找中间节点 2. { 3. struct ListNode*slow=head; 4. struct ListNode*fast=head; 5. while(fast) 6. { 7. //slow=slow->next; 8. if(fast->next==NULL) 9. { 10. break; 11. } 12. else 13. { 14. fast=fast->next->next; 15. } 16. slow=slow->next; 17. } 18. return slow; 19. } 20. 21. struct ListNode* reverseList(struct ListNode* head) //逆置链表 22. { 23. if(head==NULL) 24. return NULL; 25. struct ListNode*n1=NULL; 26. struct ListNode*n2=head; 27. struct ListNode*n3=n2->next; 28. while(n2) 29. { 30. n2->next=n1; 31. n1=n2; 32. n2=n3; 33. if(n3==NULL) 34. break; 35. n3=n3->next; 36. } 37. return n1; 38. } 39. class PalindromeList { 40. public: 41. bool chkPalindrome(ListNode* head) 42. { 43. // write code here 44. struct ListNode*mid=middleNode(head); 45. struct ListNode*rmid=reverseList(mid); 46. while(head&&rmid) //分别遍历 47. { 48. if(head->val!=rmid->val) //不相等则返回 false 49. { 50. return false; 51. } 52. head=head->next; 53. rmid=rmid->next; 54. } 55. return true; 56. } 57. };
😽本篇文章到此就结束了，若有错误或是建议，欢迎小伙伴们指出；😻
😍请多多支持博主哦~🥰
🤩谢谢你的阅读~😃
