程序员社区

力扣每日一题填坑系列——链表多题组合

目录

  • 回文链表
  • 复制带随机指针的链表
  • 两两交换链表中的结点

回文链表

题目链接

题目描述

给定一个链表的 头节点 head ,请判断其是否为回文链表。

如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。

例如:[1,2,3,3,2,1]就是一个回文链表

思路求解

我们要解这道题,就要先抓住回文链表的特征

它有什么特征?从后往前看和从前往后看相同

也就是需要:前半段链表和后半段链表相同

我们只需要:将后半段链表逆置,再依次与前半段链表比较即可

至于怎么判断链表中点和逆置,已经在前面的博客中讲到了

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

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* n1=NULL,*n2=head,*n3=head->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);
    mid=reverseList(mid);
    struct ListNode* cur1=head,*cur2=mid;
    while(cur1&&cur2)
    {
        if(cur1->val!=cur2->val)
            return false;
        cur1=cur1->next;
        cur2=cur2->next;
    }
    return true;
}

复制带随机指针的链表

题目链接

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

在这里插入图片描述

思路求解

本题需要复制上面的链表

我们可以知道,复制链表的next指针是相当简单的,但是要复制random随机指针就变得非常困难,因为random的位置我们完全不能确定

所以,我们要求解这个问题,只能将复制链表与原链表建立一个映射关系,来方便我们的复制操作

要怎么建立关系呢?

可以尝试先将每个复制结点链接到原结点的后面,这样我们就能得出以下对应关系:

先通过原链表的random找到原来链接的元素,原来的结点的下一个结点,就是我们需要链接的结点

这样,我们链接random就变得相当的容易

画图求解

复制操作:

在这里插入图片描述

链接随机结点:

在这里插入图片描述
最后只需要遍历,然后将它们的联系断开

并将复制结点链接在一个新链表头中即可

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur=head,*copy=head;
    if(!head)
        return NULL;
    while(cur)
    {
        copy=(struct Node*)malloc(sizeof(struct Node));
        copy->next=cur->next;
        copy->val=cur->val;
        cur->next=copy;
        cur=copy->next;
    }

    cur=head;
    
    while(cur)
    {
        copy=cur->next;
        if(cur->random==NULL)
            copy->random=NULL;
        else
        {
            copy->random=cur->random->next;
        }
        cur=copy->next;
        if(cur)
            copy=cur->next;
    }
    struct Node* copyhead=(struct Node*)malloc(sizeof(struct Node)),*copytail=copyhead;
    cur=head;
    
    
    while(cur)
    {
        copy=cur->next;
        struct Node* next=copy->next;
        copytail->next=copy;
        copytail=copy;
        cur->next=next;
        cur=next;
        if(cur)
        {
            copy=cur->next;
            next=copy->next;
        }
        
    }
    struct Node* returnhead=copyhead->next;
    free(copyhead);
    return returnhead;
}

两两交换链表中的结点

题目链接

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换

在这里插入图片描述

思路求解

我们在这里的话,既然是要两两交换,就定义两个指针好了

一个指针指向当前操作的一对元素,一个指针指向下一对待操作的链表

直接如下图这么交换即可

在这里插入图片描述

不过这道题有一些特殊情况需要进行讨论

首先,为空链表和只有一个结点的时候,返回其本身即可

为奇数个结点的时间呢?

如果链表是[123],就应该返回[213]

所以在结束条件中应该还对结点的next是否为空做判断

如果此时还往后遍历的话,在next=cur->next->next就造成空指针解引用了

其次,如果next为奇数结点的最后一个结点,如果按照原代码进行操作的话,第一个结点将指向NULL,所以也需要加一个特判

最后的代码如下

struct ListNode* swapPairs(struct ListNode* head){
    if(!head)
        return NULL;
    if(!head->next)
        return head;
    struct ListNode* cur=head,*next=cur->next->next;
    head=head->next;
    while(cur&&cur->next)//这里的cur->next是奇数个结点的情况
    {

        cur->next->next=cur;
        if(!next)
            cur->next=NULL;//如果next为空指向空
        else if(!next->next)
            cur->next=next;//如果为奇数的最后一个结点,就指向next本身,否则就指向NULL了
        else
            cur->next=next->next;//偶数个结点
        cur=next;
        if(next&&cur->next)//这里是防止奇数个结点错误遍历的情况
            next=cur->next->next;
    }
    return head;
}

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 力扣每日一题填坑系列——链表多题组合

一个分享Java & Python知识的社区