目录

一、有效的括号

二、复制带随机指针的链表 

一、有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对于有效的括号这道题，我们需要使用与栈相关的内容，这里可以查看我们的另外一篇博文

栈的实现（c语言数据结构）_wolfwalker的博客-CSDN博客 

先实现我们的栈，再调用我们生成的栈来完成本道题目

有效的括号就是一个括号匹配的问题，也就是说大中小三种左括号需要和对应的右括号相匹配。这里我们利用栈数据结构先入后出的特点，将我们读取到的括号依次存入我们的栈中，当我们读取到右括号的时候，立即取出栈顶的左括号，如果这个左括号和我们当前的右括号的匹配的，则我们继续读取，如果不匹配，那么字符串s就是无效的。

以下是我们的代码实现

//这一部分是我们栈的实现
#include 
#include 
#include 
#include 

#define N 10
typedef  int STDataType;
typedef struct Stack
{
    STDataType *a;
    int top;
    int capacity;
}ST;

void StackInit(ST*ps);
void StackDestory(ST*ps);
void StackPush(ST*ps,STDataType x);
void StackPop(ST*ps);
STDataType StackTop(ST*ps);
bool StackEmpty(ST*ps);

void StackInit(ST*ps)
{
    assert(ps);
    ps->a=NULL;
    ps->top=0;
    ps->capacity=0;
}
void StackDestory(ST*ps)
{
    assert(ps);
    free(ps->a);
    ps->a=NULL;
    ps->top=ps->capacity=0;
}
void StackPush(ST*ps,STDataType x)
{
    assert(ps);
    //top标记的是最后一个数据的下一个位置。
    if(ps->top==ps->capacity)
    {
        int newCapacity=ps->capacity==0?4:ps->capacity*2;
        STDataType *tmp= (STDataType *)realloc(ps->a,sizeof (STDataType)*newCapacity);
        if(tmp==NULL)
        {
            printf("reallod failn");
            exit(-1);
        }
        ps->a=tmp;
        ps->capacity=newCapacity;
    }
    ps->a[ps->top]=x;
    ps->top++;
}
void StackPop(ST*ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}
STDataType StackTop(ST*ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top-1];
}
bool StackEmpty(ST*ps)
{
    assert(ps);
    return ps->top==0;
}
int StackSize(ST*ps)
{
    assert(ps);
    return ps->top;
}

//这一部分是我们具体的括号匹配的思想的实现
bool isValid(char * s){
    assert(s);
//创建一个新的栈空间
    ST st;
//初始化我们的栈
    StackInit(&st);
//当我们传入的s没有读取完的时候，我们就不断往后读取
    while(*s)
    {
//如果我们读取到的是左括号的话，我们就将我们读取到的数据入栈
        if(*s=='('||*s=='['||*s=='{')
        {
            StackPush(&st,*s);
            ++s;
        }
//如果读取到的是我们的右括号
        else{
//首先我们需要判断当前的栈是不是空的，因为存在只有右括号没有左括号的情况
//这里调用我们之前写的StackEmpty函数来判断我们当前的栈是否是空的，
//如果是空的，我们就销毁我们的栈，并且return false
            if(StackEmpty(&st))
            {
                StackDestory(&st);
                return false;
            }
//我们取出我们的栈顶元素
            STDataType top=StackTop(&st);
            StackPop(&st);
//判断我们栈顶的括号与我们当前的括号能否匹配，如果匹配得上，我们就继续向后读取
            if((top=='{'&&*s=='}')||(top=='['&&*s==']')||(top=='('&&*s==')'))
            {
                ++s;
            }
//如果匹配不上，我们就返回false
            else
            {
                return false;
            }
        }
    }
//这里我们用一个bool类型来判断当前的栈是否为空，因为我们当前全部都已经读取完了，如果成功的话，所有的括号都应该已经一一匹配上了
    bool ret=StackEmpty(&st);
//销毁我们的栈
    StackDestory(&st);
    return ret;
}

二、复制带随机指针的链表 

给你一个长度为 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 作为传入参数。

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本道题的题意大致就是我们现在有一个链表，但是这个链表比较特别，每个结点有着指向下一个结点的指针以外，还有一个指向链表其他随机一个结点的指针。我们需要做的就是复制这个链表，包括顺序的指针和那些随机的指针，然后将我们新生成的链表的头结点返回。这也就是我们所说的深度拷贝。

这道题我们的解题思路如下

 

最后再将我们新生成的链表从原来的链表中剪下来。 

struct Node* copyRandomList(struct Node* head) {
//在每个结点之间创建copy结点来连接我们原来的链表，copy结点就是我们新生成的拷贝的结点
	struct Node* cur=head;
//创建一个临时结点，用来遍历我们的链表
    while(cur)
    {
//创建一个新的拷贝结点
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
//我们拷贝结点的数据是我们临时结点的数据，
        copy->val=cur->val;
//将我们的拷贝结点插入到我们的cur结点和cur->next结点之间的位置。
        copy->next=cur->next;
        cur->next=copy;
//将我们的cur移动到下一个需要拷贝的结点
        cur=copy->next;

    }
//此时我们已经完成步骤一，也就是说我们新的拷贝的结点已经交叉地插入到原来的链表的每两个结点之中了。



//将我们的随机指针拷贝到我们新生成的节点中。
//将我们的临时结点调到原链表的头结点，来重新遍历我们的链表
    cur=head;
    while(cur)
    {
//由于我们前一步中，我们已经把拷贝的结点插入到原来的链表的相邻的两个结点之间了，所以我们的copy结点就是我们的cur结点的next结点
        struct Node* copy=cur->next;
//如果我们的当前拷贝对象结点的random指针为null，那我们拷贝结点的random的指针也为null
        if(cur->random==NULL)
            copy->random=NULL;
//如果不是的话，我们的拷贝结点的random指针所指向的应该是我们的原来的结点的random指针的下一个结点（应为我们上一步已经将我们的拷贝链表额结点依次插入到我们的原来的链表的每两个结点之间，所以我们的random指针的next就是我们拷贝的链表的对应的位置的结点）
        else
            copy->random=cur->random->next;
//将我们的cur指针指向我们的下一个原链表的结点。
        cur=copy->next;
    }
//此时，我们已经完成了第二部，也就是说我们此时已经将我们的链表的random指针的指向完成了



//第三步我们需要将我们拷贝的结点从我们原来的混合的链表中剪下来，生成一条单独的链表
    cur=head;
//创建两个新的指针，分别指向我们的链表头和链表尾
    struct Node* copyHead=NULL,*copyTail= NULL;
    while(cur)
    {
        struct Node* copy=cur->next;
//使用next来保存我们的copy之后的那个结点，放置我们在将我们的拷贝链表中的结点从我们的原链表中剪下来之后，找不到后面的结点。
        struct Node* next=copy->next;
//如果我们当前copytail为空，也就是说我们当前的拷贝链表中没有一个元素，这时，将我们的拷贝链表的头指针和尾指针都指向我们的copy结点。也就是说我们当前的拷贝链表只有一个结点，此时我们的头指针和尾指针都指向这个结点

        if(copyTail==NULL)
        {
            copyHead=copyTail=copy;
        }
//如果不是拷贝链表中的第一个结点，我们将我们当前的copy结点尾插到我们的新生成的链表中，然后将我们的尾指针后移
        else
        {
            copyTail->next=copy;
            copyTail=copyTail->next;
        }
//将我们原来的链表恢复
        cur->next=next;
//将我们的遍历指针移动到下一个结点位置。
        cur=next;
        
    }
//将我们新生成的链表返回。
    return copyHead;
}