【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

 

目录

一.【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->val<cur2->val){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(n1<n2){longlist=headB;shortlist=headA;}while(gap--){longlist=longlist->next;}   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 herestruct 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;}
};

---

😽本篇文章到此就结束了，若有错误或是建议，欢迎小伙伴们指出；😻

😍请多多支持博主哦~🥰

🤩谢谢你的阅读~😃