OJ第四篇

链表分割

链接: 链表分割

虽然这个题牛客网中只有C++,但是无所谓，我们只要知道C++是兼容C的就可以了

至于说这个题的思路，我们就弄两个链表，把小于x的结点放到一个链表中，剩下的放到另一个链表中，最后把两个链表串起来就可以了

实现方式的话有两种，一种是链表带哨兵位，一种是不带，带哨兵位的话处理起来比较简单，很多判断条件是不需要的，不带的话就相对要麻烦一些，但是你如果对链表的操作比较熟悉的话，其实还行

下面是带哨兵位的实现

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode *cur=pHead;
        struct ListNode *head1,*head2,*tail1,*tail2;//1的是小值，2的是大值
        //开辟哨兵位
        head1=tail1=(struct ListNode *)malloc(sizeof(struct ListNode ));
        head2=tail2=(struct ListNode *)malloc(sizeof(struct ListNode ));
while(cur){
     struct ListNode *next=cur->next;
     if(cur->val<x){
        tail1->next=cur;
        tail1=tail1->next;
        tail1->next=NULL;
     }
     else{
         tail2->next=cur;
        tail2=tail2->next;
        tail2->next=NULL;
     }
     cur=next;
}
//把两个链表接到一起，如果第一个链表为空也无所谓
tail1->next=head2->next;
 struct ListNode *head=head1->next;
 free(head1);//没用的就free掉
 free(head2);
return head;
 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

下面是不带哨兵位的实现

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
 struct ListNode *cur=pHead;
 struct ListNode *head1=NULL,*head2=NULL,*tail1=NULL,*tail2=NULL;//一般都是定义两组指针，一组管理一个链表
 while(cur){
    struct ListNode *tmp=cur;
    cur=cur->next;
    if(tmp->val<x){
if(tail1==NULL){//如果链表为空
    head1=tail1=tmp;
    tail1->next=NULL;
}
else{
    tail1->next=tmp;
    tail1=tail1->next;
    tail1->next=NULL;
}
    }
    else{
if(tail2==NULL){
    head2=tail2=tmp;
    tail2->next=NULL;
}
else{
    tail2->next=tmp;
    tail2=tail2->next;
    tail2->next=NULL;
}
    }
 }
 //合并两个链表
 if(head1==NULL){//判断第一个表是否为空
    return head2;
 }
 else{
    tail1->next=head2;
    return head1;
 }
 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

环形链表

链接：环形链表

这个题的话需要一些数学推理去找它们之间的关系，要不然不太好说

我们假如说起始位置到入环处的距离为a，入环出到相遇处距离为b，环的周长为c，在之前，我们已经能判断一个链表中是否有环了，就是通过两个指针，一个fast一回走两步，一个slow一回走一步，那么它们两个之间有一定的数学关系，就是2*(a+b)=a+nc+b,化简一下为c-b+c(n-1)=a,这是什么意思啊？就是一个指针从头走，一个指针从相遇处走，以相同的速度，最后就会在那个相遇入环点相遇

下面我们来实现一下

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast=head,*slow=head;
while(fast&&fast->next){//能出循环就没有环，有环在循环中返回
fast=fast->next->next;
slow=slow->next;
    if(fast==slow){
struct ListNode *tmp=fast;
while(tmp!=head){//相同时停止，并返回这个点
tmp=tmp->next;
head=head->next;
}
return head;
    }
}
return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

我们之前找过两个相交链表的相交位置，这里我们如果把相遇点的前一个位置的next置为空，就可以了，需要注意前一个只能是fast的前一个

下面我们来实现一下

//找相交点的函数
//思路就是计算两个链表的长度，长的先走差的长度数，最后同时走，相同了就找到了
struct ListNode *meetpoint(struct ListNode *s1,struct ListNode *s2){
    int num1=0;
    int num2=0;
    struct ListNode *head1=s1,*head2=s2;
    while(head1){
        num1++;
        head1=head1->next;
    }
    while(head2){
        num2++;
        head2=head2->next;
    }
    struct ListNode *thelong=s1,*theshort=s2;
    if(num2>num1){
        thelong=s2;
        theshort=s1;
    }
    int num=abs(num1-num2);//求差的长度数
    while(num){
        thelong=thelong->next;
        num--;
    }
    while(thelong!=theshort){
        thelong=thelong->next;
        theshort=theshort->next;
    }
    return thelong;
}

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast=head,*slow=head;
while(fast&&fast->next){
    struct ListNode *fastprev=fast->next;//记录一下fast的上个位置
fast=fast->next->next;

slow=slow->next;
    if(fast==slow){
 fastprev->next=NULL;
 return meetpoint(head,slow);
    }
}
return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

有效的括号

链接：有效的括号

这个题是用栈来实现的，正好利用了栈的特性，左括号入栈，右括号判断出栈，如果不匹配就返回false

bool isValid(char * s){
    ST st;
    STInit(&st);
while(*s){
    if(*s=='('||*s=='['||*s=='{'){//左括号入栈
        STPush(&st,*s);
    }
    else{
			if(STEmpty(&st)){//栈为空并且要处理的字符为右括号
				STDestroy(&st);
				return false;
			}
        char tmp=STTop(&st);//匹配栈顶元素和要处理的元素
        if(*s==')'&&tmp!='('||*s==']'&&tmp!='['||*s=='}'&&tmp!='{'){
            return false;
        }
        else{
            STPop(&st);
        }
    }
    s++;
}
if(!STEmpty(&st)){//true的话最后栈应该为空
STDestroy(&st);
    return false;
}
else{
	STDestroy(&st);
    return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

我们在这个函数之前是需要自己创建栈的，并且要实现它的一些功能，我们之前也有代码，可以看之前的博客
链接：栈和队列