目录
一.【Leetcode206】反转链表
1.链接
2.题目再现
3.解法A:三指针法
二.【Leetcode21】合并两个有序链表
1.链接
2.题目再现
3.三指针尾插法
三.【Leetcode160】相交链表
1.链接
2.题目再现
3.解法
四.链表的回文结构
1.链接
2.题目再现
3.解法
一.【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。
动态演示:
三指针动态演示
代码:
struct ListNode* reverseList(struct ListNode* head) { if(head==NULL) return NULL; struct ListNode*n1=NULL; struct ListNode*n2=head; struct ListNode*n3=n2->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3==NULL) break; n3=n3->next; } return n1;}
二.【Leetcode21】合并两个有序链表
1.链接
合并两个有序链表
2.题目再现
3.三指针尾插法
思路:创建一个新的链表,分别遍历两个链表,小的就尾插到新链表,然后指针向后走一步,直到有一方为空时就结束循环;结束循环后,判断哪个链表不为空,把不为空的尾插到新链表中去。
1.定义指针cur1=list1,cur2=list2,建立新的链表newlist,和保存新链表尾节点的指针tail;
2.注意:在遍历前要先判断两链表是否为空,若一方为空,则直接返回另一方;
3.分表遍历两个链表,比较其值,小的尾插到新链表,并向后走一步(如果一样大,那么随便取哪一个都行);
4.结束循环后,判断哪个链表不为空,尾插到新链表。
动态演示:
合并两个有序链表动态演示
代码:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if(list1==NULL) return list2; if(list2==NULL) return list1; struct ListNode*newlist=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode*cur1=list1; struct ListNode*cur2=list2; struct ListNode*tail=newlist; //newlist->next=tail; while(cur1&&cur2) { if(cur1->valval) { tail->next=cur1; tail=tail->next; cur1=cur1->next; } else { tail->next=cur2; tail=tail->next; cur2=cur2->next; } } if(cur1) { tail->next=cur1; } if(cur2) { tail->next=cur2; } struct ListNode*head=newlist->next; free(newlist); newlist=NULL; return head;}
三.【Leetcode160】相交链表
1.链接
相交链表
2.题目再现
3.解法
1.先分别遍历两个链表,记录下两个链表的长度;
2.如果两个链表尾节点的地址一样,则说明它们相交,否则不相交,(注意是地址不是值);
3.求出两个链表长度的差gap;
4.先让长的链表走差距步gap,短的链表先不动;
5.然后两个链表同时走一步,比较每走一步时两个链表当前节点的地址,如果一样,则说明找到了它们相交的起始位置,返回。
动态演示:
相交链表动态演示
代码:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode*tailA=NULL; struct ListNode*tailB=NULL; int n1=0,n2=0; struct ListNode*cur1=headA,*cur2=headB; while(cur1) { n1++; tailA=cur1; cur1=cur1->next; } while(cur2) { n2++; tailB=cur2; cur2=cur2->next; } if(tailA!=tailB) return NULL; int gap=n1-n2; if(gap<0) gap=-gap; struct ListNode*longlist=headA,*shortlist=headB; if(n1next; } while(longlist!=shortlist) { longlist=longlist->next; shortlist=shortlist->next; } return longlist;}
四.链表的回文结构
1.链接
链表的回文结构
2.题目再现
3.解法
首先我们得知道什么是回文结构?
简单来说,回文结构不管是正着读还是倒着读,结果是一样的;
我们就可以利用这一点来解决这道题。
1.找到链表的中间节点;
2.逆置链表中间节点以后的部分,rmid 为后半部分逆置后的第一个节点;
3.头指针 head 和 rmid 同时向后遍历,若 head 的值不等于 rmid 的值,则不是回文结构,返回 false ,循环结束后则是回文结构,返回 true 。
动态演示:
回文链表动态演示
代码:
struct ListNode* middleNode(struct ListNode* head) //找中间节点{ struct ListNode*slow=head; struct ListNode*fast=head; while(fast) { //slow=slow->next; if(fast->next==NULL) { break; } else { fast=fast->next->next; } slow=slow->next; } return slow;}struct ListNode* reverseList(struct ListNode* head) //逆置链表{ if(head==NULL) return NULL; struct ListNode*n1=NULL; struct ListNode*n2=head; struct ListNode*n3=n2->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3==NULL) break; n3=n3->next; } return n1;}class PalindromeList {public: bool chkPalindrome(ListNode* head) { // write code here struct ListNode*mid=middleNode(head); struct ListNode*rmid=reverseList(mid); while(head&&rmid) //分别遍历 { if(head->val!=rmid->val) //不相等则返回 false { return false; } head=head->next; rmid=rmid->next; } return true; }};
本篇文章到此就结束了,若有错误或是建议,欢迎小伙伴们指出;
请多多支持博主哦~
谢谢你的阅读~