目录

一.【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;    }};

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

请多多支持博主哦~

谢谢你的阅读~