您现在的位置是:首页 >学无止境 >LeetCode 链表OJ分享网站首页学无止境

LeetCode 链表OJ分享

fun- 2024-06-17 10:14:28
简介LeetCode 链表OJ分享

删除排序链表中的重复元素

链接: link
题目描述:
在这里插入图片描述
题目思路:

本题思路使用双指针,以示例二为例如下图:
在这里插入图片描述

如果head->val等于next->val,那么此时就要删除重复节点next,具体步骤:
1、创建一个节点指针del记录被删除的节点next
2、next指针向下移动
3、free(del)
4、链接cur和next,cur->next=next

在这里插入图片描述

如果head->val不等于next->val,那么此时就要向下移动节点指针,具体步骤:
cur=next;
next=next->next

在这里插入图片描述

循环结束条件:当next指针指向空时,循环结束,返回链表的头

在这里插入图片描述

本题注意两点:
1、注意链表只有一个节点时,不做删除重复元素的操作,直接返回链表的头。
2、注意如果该链表为空链表,直接返回NULL。

代码实现:

struct ListNode* deleteDuplicates(struct ListNode* head)
{
    if(head==NULL)
    {
        return NULL;
    }
    if((head->next)==NULL)
    {
        return head;
    }
    struct ListNode* cur = head;
    struct ListNode* next = cur->next;
    while(next)
    {
        if(cur->val==next->val)
        {
            struct ListNode* del = next;
            next = next->next;
            cur->next = next;
            free(del);
        }
        else
        {
            cur=cur->next;
            next = next->next;
        }
    }
    return head;
}

回文链表

链接: link
题目描述:
在这里插入图片描述
题目思路:
本题主要核心步骤分为两三大步,第一步就是寻找中间节点,第二步逆置中间节点后的其他节点,第三步分别从头节点和中间节点开始,对比元素是否相等,如果相等为回文链表返回true,不相等返回false。

第一步:寻找中间节点
思路:快慢指针,快指针一次走两步,慢指针一次走一步

偶数节点循环结束条件分析:
循环结束条件为fast=NULL

在这里插入图片描述
在这里插入图片描述
奇数节点循环结束条件分析:
循环结束条件为fast->next=NULL

在这里插入图片描述
在这里插入图片描述
第一步代码实现:

struct ListNode* MiddleNode(struct ListNode* head)
 {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast = fast->next->next;
    }
    return slow;
 }

第二步:逆置中间节点后的节点
思路:改变链表指向,返回逆置后链表新的头

在这里插入图片描述
在这里插入图片描述

1、三个指针n1 n2 n3,逆置以下图为例

在这里插入图片描述

改变n2的指向,n2->next=n1

在这里插入图片描述

3个指针同时后移:n1=n2 n2=n3 n3=n3->next

在这里插入图片描述

循环上述步骤操作

循环结束条件分析:
本题循环结束条件为n2为空,但是n2为空的同时还要注意n3指针的空指针问题,如下图,n1到达最后一个节点,此时n2刚好为空,但是n3在上述迭代的情况下,下图的位置显然是不正确的。
在这里插入图片描述
此处应该注意加以判断n3是否为空,如果n3为空,则不再进行向下移动的迭代,最后返回n1,即为逆置后链表新的头。
在这里插入图片描述
第二步代码实现:

struct ListNode* reverseNode(struct ListNode* mid)
 {
     struct ListNode* n1 = NULL;
     struct ListNode* n2 = mid;
     struct ListNode* n3 = mid->next;
     while(n2)
     {
         n2->next = n1;
         //迭代
         n1=n2;
         n2=n3;
         if(n3)
         {
             n3=n3->next;
         }
     }
     return n1;
 }

第三步分别从头节点和中间节点开始,对比元素是否相等,如果相等为回文链表返回true,不相等返回false。

经过上述两个步骤的修改后,链表的形态如下图:
在这里插入图片描述
对比元素是否相等,循环结束条件:rmid!=NULL
代码实现:

struct ListNode* MiddleNode(struct ListNode* head)
 {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast = fast->next->next;
    }
    return slow;
 }
 struct ListNode* reverseNode(struct ListNode* mid)
 {
     struct ListNode* n1 = NULL;
     struct ListNode* n2 = mid;
     struct ListNode* n3 = mid->next;
     while(n2)
     {
         n2->next = n1;
         //迭代
         n1=n2;
         n2=n3;
         if(n3)
         {
             n3=n3->next;
         }
     }
     return n1;
 }
bool isPalindrome(struct ListNode* head)
{
    struct ListNode* mid = MiddleNode(head);
    struct ListNode* rmid = reverseNode(mid);
    struct ListNode* cur = head;
    while(rmid)
    {
        if(cur->val==rmid->val)
        {
            cur=cur->next;
            rmid=rmid->next;
        }
        else
        {
            return false;
        }
    }
    return true;
}

剑指Offer 06.从尾到头打印链表

链接: link
题目描述:
在这里插入图片描述
题目思路:

思路同上题: 1、逆置链表,改变链接方向
2、求出链表节点的个数returnSize
3、动态开辟数组,数组元素个数为
returnSize
4、释放动态开辟的内存空间

代码实现:

 int countList(struct ListNode* head)
 {
     int count=0;
     struct ListNode* cur = head;
     while(cur)
     {
         count++;
         cur=cur->next;
     }
     return count;
 }
 struct ListNode* reverseList(struct ListNode* head)
 {
     if(head==NULL)
     {
         return NULL;
     }
     if(head->next==NULL)
     {
         return head;
     }
     struct ListNode* n1 = NULL;
     struct ListNode* n2 = head;
     struct ListNode* n3 = head->next;
     while(n2)
     {
         n2->next = n1;
         n1 = n2;
         n2=n3;
         if(n3)
         {
            n3=n3->next;
         }
     }
     return n1;
 }
int* reversePrint(struct ListNode* head, int* returnSize)
{
    int ret = countList(head);
    *returnSize = ret;
    struct ListNode* newhead = reverseList(head);
    int * tmp = (int*)malloc(sizeof(int)*(*returnSize));
    if(tmp==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    struct ListNode* cur = newhead;
    int i = 0;
    while(i<ret&&cur)
    {
         tmp[i]=cur->val;
         cur=cur->next;
         i++;
    }
    return tmp;
    free(tmp);
    tmp=NULL;
}

复制带随机指针的链表

链接: link
题目描述:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
题目思路:
1、拷贝节点插入到原节点后面
在这里插入图片描述
步骤:

1、画图明确拷贝节点和原节点

在这里插入图片描述

2、动态开辟一个内存空间存放拷贝节点
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
将原节点的值赋值给拷贝节点 copy->val=cur->val

3、链接拷贝节点

在这里插入图片描述

4、循环条件:cur!=NULL,循环进行上述步骤

2、控制拷贝节点的random:copy->random=cur->random->next;
在这里插入图片描述
步骤:

1、此时copy节点就在cur节点的后面,cur->next = copy

在这里插入图片描述

2、如果cur原节点的random为空,那么拷贝节点的random也为空

在这里插入图片描述

3、如果原节点的random不为空,拷贝节点的random和原节点的random相等,copy->random=cur->random->next;拷贝节点的random在原节点random的下一个节点。

在这里插入图片描述

4、迭代向下,cur=copy->next

3、拷贝节点从原链表上解下来尾插形成新的链表,并且恢复原链表(具体看图实现)
步骤:

1、将拷贝节点尾插到新的链表

在这里插入图片描述

2、恢复原链表(依次按原链表链接)

在这里插入图片描述

struct Node* copyRandomList(struct Node* head) 
{
    //1、将拷贝节点链接到原节点的后面
    struct Node* cur = head;
    while(cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        //链接
        struct Node* next = cur->next;
        cur->next = copy;
        copy->next = next;
        cur=next;
    }
    //2、控制拷贝节点的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        cur=copy->next;
    }
    //3、尾插新链表,恢复原链表
    cur = head;
    struct Node* copyHead = NULL,* copyTail = NULL;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if(copyHead==NULL)
        {
            copyHead = copyTail=copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail=copyTail->next;
        }
        //恢复原链表
        cur->next = next;
        cur= next;

    }
    return copyHead;
	
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。