?文章來源地址http://www.zghlxwxcb.cn/news/detail-784580.html

目錄

一.【Leetcode206】反轉(zhuǎn)鏈表

1.鏈接

2.題目再現(xiàn)

?3.解法A：三指針法

二.【Leetcode21】合并兩個有序鏈表

1.鏈接

2.題目再現(xiàn)

?3.三指針尾插法

三.【Leetcode160】相交鏈表

1.鏈接

2.題目再現(xiàn)

3.解法

四.鏈表的回文結(jié)構(gòu)

1.鏈接

2.題目再現(xiàn)

?3.解法

一.【Leetcode206】反轉(zhuǎn)鏈表

1.鏈接

反轉(zhuǎn)鏈表

2.題目再現(xiàn)

?3.解法：三指針法

1.定義三個指針n1 n2 n3，n1指向空，n2指向頭節(jié)點，n3指向頭節(jié)點的next；

2.注意：要先判斷是否是空鏈表；

3.用n2遍歷鏈表，n2為空時就跳出循環(huán)；

4.翻轉(zhuǎn)鏈表，即n2->next=n1；

5.翻轉(zhuǎn)下一個節(jié)點，即n1=n2；n2=n3；n3=n3->next；

6.注意：在n3=n3->next前要先判斷n3是否為空，若為空就結(jié)束循環(huán)，否則可能會發(fā)生對空指針的解引用；

7.n1為反轉(zhuǎn)后的頭節(jié)點，返回n1。

動態(tài)演示：

代碼：

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.題目再現(xiàn)

?3.三指針尾插法

思路：創(chuàng)建一個新的鏈表，分別遍歷兩個鏈表，小的就尾插到新鏈表，然后指針向后走一步，直到有一方為空時就結(jié)束循環(huán)；結(jié)束循環(huán)后，判斷哪個鏈表不為空，把不為空的尾插到新鏈表中去。

1.定義指針cur1=list1，cur2=list2，建立新的鏈表newlist，和保存新鏈表尾節(jié)點的指針tail；

2.注意：在遍歷前要先判斷兩鏈表是否為空，若一方為空，則直接返回另一方；

3.分表遍歷兩個鏈表，比較其值，小的尾插到新鏈表，并向后走一步（如果一樣大，那么隨便取哪一個都行）；

4.結(jié)束循環(huán)后，判斷哪個鏈表不為空，尾插到新鏈表。

動態(tài)演示：

代碼：

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.題目再現(xiàn)

3.解法

1.先分別遍歷兩個鏈表，記錄下兩個鏈表的長度；

2.如果兩個鏈表尾節(jié)點的地址一樣，則說明它們相交，否則不相交，（注意是地址不是值）；

3.求出兩個鏈表長度的差gap；

4.先讓長的鏈表走差距步gap，短的鏈表先不動；

5.然后兩個鏈表同時走一步，比較每走一步時兩個鏈表當前節(jié)點的地址，如果一樣，則說明找到了它們相交的起始位置，返回。?

動態(tài)演示：

代碼：

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;
}

四.鏈表的回文結(jié)構(gòu)

1.鏈接

鏈表的回文結(jié)構(gòu)

2.題目再現(xiàn)

?3.解法

首先我們得知道什么是回文結(jié)構(gòu)？

簡單來說，回文結(jié)構(gòu)不管是正著讀還是倒著讀，結(jié)果是一樣的；

我們就可以利用這一點來解決這道題。

1.找到鏈表的中間節(jié)點；

2.逆置鏈表中間節(jié)點以后的部分，rmid 為后半部分逆置后的第一個節(jié)點；

3.頭指針 head 和 rmid 同時向后遍歷，若 head 的值不等于 rmid 的值，則不是回文結(jié)構(gòu)，返回 false ，循環(huán)結(jié)束后則是回文結(jié)構(gòu)，返回 true 。

動態(tài)演示：

代碼：

struct ListNode* middleNode(struct ListNode* head)   //找中間節(jié)點
{
    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;
    }
};

??本篇文章到此就結(jié)束了，若有錯誤或是建議，歡迎小伙伴們指出；??

??請多多支持博主哦~??

??謝謝你的閱讀~??

?

到了這里，關(guān)于【Leetcode】反轉(zhuǎn)鏈表 合并鏈表 相交鏈表 鏈表的回文結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！