《C语言实现链表相交、带环问题》_c语言带环与相交链表问题

作者：小舞很执着 | 2024-07-19 17:35:13

踩

c语言带环与相交链表问题

例题：

//1.判断单链表是否带环？若带环，求环的长度？求环的入口点？
//2.判断两个链表是否相交，若相交，求交点。（假设链表不带环）
//3.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】
//4.复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个节点，
//还有一个random指针指向这个链表中的一个随机节点或者NULL，
//现在要求实现复制这个链表，返回复制后的新链表。
////ps: 复杂链表的结构 
//struct ComplexNode
//{
//  int _data; // 数据 
//  struct ComplexNode * _next; // 指向下一个节点的指针 
//  struct ComplexNode * _random; // 指向随机节点（可以是链表中的任意节点 or 空） 
//};1
2
3
4
5
6
7
8
9
10
11
12
13

基本函数：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<math.h>

typedef int DataType;//节点中数据类型

typedef struct ListNode//节点数据结构
{
    DataType data;
    struct ListNode *next;
} ListNode;


ListNode *Find(ListNode *plist,DataType x)//查找函数，返回查找到节点的地址
{
    ListNode *cur = plist;
    while (cur)
    {
        if ((cur->data) == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return cur;
}


ListNode *BuyNode(DataType x)//产生一个节点并把节点中的数据置数，返回节点地址
{
    ListNode *plist = (ListNode *)malloc(sizeof(ListNode));
    if (plist != NULL)
    {
        plist->data = x;
        plist->next = NULL;
        return plist;
    }
    return NULL;
}



void PrintList(ListNode *plist)//打印单链表
{
    assert(plist != NULL);
    while (plist)
    {
        printf("%d->",plist->data);
        plist = plist->next;
    }
    printf("NULL\n");
}

void PushBuck(ListNode **pplist,DataType x)//在函数尾部插入节点
{
    ListNode *cur = NULL;
    assert(pplist);
    cur = *pplist;
    if (*pplist == NULL)
    {
        *pplist = BuyNode(x);
        return;
    }
    while ((cur->next) != NULL)
    {
        cur = cur->next;
    }
    cur->next = BuyNode(x);
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

1.判断单链表是否带环？若带环，求环的长度？求环的入口点？

思路：
这里写图片描述

ListNode *IsCycle(ListNode *plist)//判断是否带环
{
    ListNode *fast = plist;
    ListNode *slow = plist;
    assert(plist);
    while ((fast != NULL) && (fast->next != NULL))
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
            return fast;
    }
    return NULL;
}

int GetCycleLen(ListNode *meetnode)//求环的长度
{
    ListNode *cur = NULL;
    int count = 1;
    assert(meetnode);
    cur = meetnode->next;
    while (cur != meetnode)
    {
        cur = cur->next;
        count++;
    }
    return count;
}

ListNode *GetCycleEnter(ListNode *plist, ListNode *meetnode)//求环的入口点
{
    assert(plist);
    assert(meetnode);
    while (plist != meetnode)
    {
        plist = plist->next;
        meetnode = meetnode->next;
    }
    return plist;
}

void Test()
{
    ListNode *plist = NULL;
    ListNode *tmp1 = NULL;
    ListNode *tmp2 = NULL;
    ListNode *tmp = NULL;
    PushBuck(&plist, 1);
    PushBuck(&plist, 2);
    PushBuck(&plist, 3);
    PushBuck(&plist, 4);
    PushBuck(&plist, 5);
    PushBuck(&plist, 6);
    PushBuck(&plist, 7);


    tmp1 = Find(plist, 3);
    tmp2 = Find(plist, 7);
    tmp2->next = tmp1;
    tmp = IsCycle(plist);
    if (tmp == NULL)
        printf("不带环！\n");
    else
    {
        printf("带环！\n");
        printf("环的长度为：%d\n",GetCycleLen(tmp));
        printf("环的入口点为：%d\n",GetCycleEnter(plist,tmp)->data);
    }
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

结果：
这里写图片描述

2.判断两个链表是否相交，若相交，求交点。（假设链表不带环）

bool CheckIsMeet(ListNode *plist1,ListNode *plist2)//判断是否相交
{
    assert(plist1);
    assert(plist2);
    while (plist1->next != NULL)
    {
        plist1 = plist1->next;
    }
    while (plist2->next != NULL)
    {
        plist2 = plist2->next;
    }
    if (plist1 == plist2)
    {
        return true;
    }
    else
    {
        return false;
    }
}

ListNode *AnswerMeetNode(ListNode *plist1,ListNode *plist2)//若相交，求交点
{
    int count1 = 0;
    int count2 = 0;
    int count = 0;
    ListNode *cur1 = plist1;
    ListNode *cur2 = plist2;
    while (cur1 != NULL)
    {
        count1++;
        cur1 = cur1->next;
    }
    while (cur2 != NULL)
    {
        count2++;
        cur2 = cur2->next;
    }
    count = count1 - count2;
    if (count > 0)
    {
        while (count--)
        {
            plist1 = plist1->next;
        }
    }
    else
    {
        count = -count;
        while (count--)
        {
            plist2 = plist2->next;
        }
    }
    while (plist1 != plist2)
    {
        plist1 = plist1->next;
        plist2 = plist2->next;
    }
    return plist1;
}

void Test1()
{
    ListNode *plist1 = NULL;
    ListNode *plist2 = NULL;
    ListNode *tmp1 = NULL;
    ListNode *tmp2 = NULL;
    bool flag = true;
    PushBuck(&plist1, 1);
    PushBuck(&plist1, 3);
    PushBuck(&plist1, 5);
    PushBuck(&plist1, 7);
    PushBuck(&plist1, 8);
    PushBuck(&plist1, 9);
    PushBuck(&plist1, 10);

    PushBuck(&plist2, 2);
    PushBuck(&plist2, 4);
    PushBuck(&plist2, 6);

    tmp1 = Find(plist2, 6);
    tmp2 = Find(plist1, 7);
    tmp1->next = tmp2;
    flag = CheckIsMeet(plist1, plist2);
    if (flag)
    {
        printf("相交！\n");
        printf("交点为：%d\n",AnswerMeetNode(plist1,plist2)->data);
    }
    else
    {
        printf("不想交！\n");
    }
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

结果：
这里写图片描述

3.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】

思路：
这里写图片描述

RetuenNoode CheckIsMeetTop(ListNode *plist1, ListNode *plist2)//判断两个链表是否相交，若相交，求交点.（假设链表可能带环）【升级版】
{
    ListNode *tmp1 = NULL;
    ListNode *tmp2 = NULL;
    RetuenNoode ret = { 0, NULL, NULL };
    assert(plist1);
    assert(plist2);
    tmp1 = IsCycle(plist1);
    tmp2 = IsCycle(plist2);
    if ((tmp1 == NULL) && (tmp2 == NULL))
    {
        //都不带环
        tmp1 = plist1;
        tmp2 = plist2;
        while (tmp1->next != NULL)
        {
            tmp1 = tmp1->next;
        }
        while (tmp2->next != NULL)
        {
            tmp2 = tmp2->next;
        }
        if (tmp1 == tmp2)
        {
            //相交
            ret.plist1 = AnswerMeetNode(plist1, plist2);
            ret.flag = 1;
            return ret;
        }
        else
        {
            //不相交
            ret.flag = 1;
            return ret;
        }
    }
    else if ((tmp1 != NULL) && (tmp2 != NULL))
    {
        //两者都带环
        ListNode *tmp = tmp1->next;
        while ((tmp != tmp2) && (tmp != tmp1))
        {
            tmp = tmp->next;
        }
        if (tmp == tmp2)
        {
            //相交
            tmp1 = GetCycleEnter(plist1,tmp1);
            tmp2 = GetCycleEnter(plist2,tmp2);
            if (tmp1 == tmp2)
            {
                //交点在链上
                int count1 = 0;
                int count2 = 0;
                int count = 0;
                ListNode *cur1 = plist1;
                ListNode *cur2 = plist2;
                while (cur1 != tmp1)
                {
                    count1++;
                    cur1 = cur1->next;
                }
                while (cur2 != tmp1)
                {
                    count2++;
                    cur2 = cur2->next;
                }
                count = count1 - count2;
                if (count > 0)
                {
                    while (count--)
                    {
                        plist1 = plist1->next;
                    }
                }
                else
                {
                    count = -count;
                    while (count--)
                    {
                        plist2 = plist2->next;
                    }
                }
                while (plist1 != plist2)
                {
                    plist1 = plist1->next;
                    plist2 = plist2->next;
                }
                ret.plist1 = plist1;
                ret.flag = 3;
                return ret;
            }
            else
            {
                //两个交点都在环上
                ret.plist1 = tmp1;
                ret.plist2 = tmp2;
                ret.flag = 3;
                return ret;
            }
        }
        else
        {
            //不相交
            ret.flag = 3;
            return ret;
        }
    }
    else
    {
        //一个带环，一个不带环。必不相交
        ret.flag = 2;
        return ret;
    }
}


void Test2()
{
    RetuenNoode ret = {0,NULL,NULL};
    ListNode *plist1 = NULL;
    ListNode *plist2 = NULL;
    ListNode *tmp1 = NULL;
    ListNode *tmp2 = NULL;
    PushBuck(&plist1, 1);
    PushBuck(&plist1, 3);
    PushBuck(&plist1, 5);
    PushBuck(&plist1, 7);
    PushBuck(&plist1, 8);
    PushBuck(&plist1, 9);
    PushBuck(&plist1, 10);

    PushBuck(&plist2, 0);
    PushBuck(&plist2, 2);
    PushBuck(&plist2, 4);
    PushBuck(&plist2, 6);

    tmp1 = Find(plist1, 10);//第三类相交 b> 2>
    tmp2 = Find(plist1, 7);
    tmp1->next = tmp2;
    tmp1 = Find(plist1, 9);
    tmp2 = Find(plist2, 6);
    tmp2->next = tmp1;

    //tmp1 = Find(plist1, 10);//第三类相交 b> 1>
    //tmp2 = Find(plist1, 7);
    //tmp1->next = tmp2;
    //tmp1 = Find(plist1, 5);
    //tmp2 = Find(plist2, 6);
    //tmp2->next = tmp1;

    //tmp1 = Find(plist2, 2);//第三类不相交
    //tmp2 = Find(plist2, 6);
    //tmp2->next = tmp1;
    //tmp1 = Find(plist1, 7);
    //tmp2 = Find(plist1, 10);
    //tmp2->next = tmp1;

    //tmp1 = Find(plist1, 7);//第二类不相交
    //tmp2 = Find(plist1, 10);
    //tmp2->next = tmp1;

    //第一类不相交

    //tmp1 = Find(plist2, 6);//第一类相交
    //tmp2 = Find(plist1, 7);
    //tmp1->next = tmp2;

    ret = CheckIsMeetTop(plist1,plist2);
    if (ret.flag == 3)
    {
        if ((ret.plist1) && (ret.plist2))
        {
            printf(" 第三类 -> b> -> 2> :\nMeetNode1:%d\nMeetNode2:%d\n", ret.plist1->data, ret.plist2->data);
        }
        else if (ret.plist1)
        {
            printf("第三类 -> b> -> 1> :\nMeetNode:%d\n", ret.plist1->data);
        }
        else
        {
            printf("第三类不相交!\n");
        }
    }
    else if (ret.flag == 1)
    {
        if (ret.plist1)
        {
            printf("第一类相交:\nMeetNode:%d\n", ret.plist1->data);
        }
        else
        {
            printf("第一类不相交!\n");
        }
    }
    else
    {
        printf("第二类不相交!\n");
    }
}

int main()
{
    //Test();
    //Test1();
    Test2();
    return 0;
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

结果：

这里写图片描述

4.复杂链表的复制。

思路：
这里写图片描述

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int DataType;

typedef struct ComplexNode
{
    DataType data;//数据
    struct ComplexNode *next;//指向下一个节点
    struct ComplexNode *random;//指向随机节点
} ComplexNode;

ComplexNode *BuyNode(DataType x)//产生新节点
{
    ComplexNode *tmp = (ComplexNode *)malloc(sizeof(ComplexNode));
    tmp->data = x;
    tmp->next = NULL;
    tmp->random = NULL;
    return tmp;
}

void PushBack(ComplexNode **pplist,DataType x)//尾插函数
{
    ComplexNode *cur = NULL;
    assert(pplist);
    cur = *pplist;
    if (*pplist == NULL)
    {
        *pplist = BuyNode(x);
    }
    else
    {
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = BuyNode(x);
    }
}

ComplexNode *FindComplexNode(ComplexNode *plist,DataType x)//查找函数
{
    if (plist == NULL)
    {
        return NULL;
    }
    else
    {
        while (plist)
        {
            if (plist->data == x)
                return plist;
            plist = plist->next;
        }
        return NULL;
    }
}

ComplexNode *LineComplexNode(ComplexNode *plist)//第一步、产生节点并连接节点
{
    ComplexNode *phead = plist;
    ComplexNode *tmp = NULL;
    ComplexNode *ret = NULL;
    assert(plist);  
    while (plist)
    {
        ret = plist->next;
        tmp = BuyNode(plist->data);
        tmp->next = plist->next;
        plist->next = tmp;
        tmp->random = NULL;
        plist = ret;
    }
    return phead;
}

void RandomEvaluate(ComplexNode *plist)//第二步、random指针赋值
{
    assert(plist);
    while (plist)
    {
        if (plist->random == NULL)
        {
            plist->next->random = NULL;
        }
        else
        {
            plist->next->random = plist->random->next;
        }
        plist = plist->next->next;
    }
}

void PrintComplexNode(ComplexNode *plist)//打印节点
{
    while (plist)
    {
        printf("%d->",plist->data);
        plist = plist->next;
    }
    printf("NULL\n");
}

void PrintRandom(ComplexNode *plist)//打印random指向的数据
{
    while (plist)
    {
        if (plist->random == NULL)
        {
            printf("NULL->");
        }
        else
        {
            printf("%d->", plist->random->data);
        }
        plist = plist->next;
    }
    printf("STOP\n");
}

ComplexNode *ToPickComplexList(ComplexNode *plist)//摘出复杂链表
{
    ComplexNode *phead = NULL;
    ComplexNode *cur = NULL;
    ComplexNode *tmp = NULL;
    if (plist == NULL)
    {
        return NULL;
    }
    while (plist)
    {
        cur = plist->next;
        plist->next = cur->next;
        if (phead == NULL)
            phead = tmp = cur;
        else
        {
            tmp->next = cur;
            tmp = cur;
        }
        plist = plist->next;
    }
    return phead;
}

void Test()
{
    ComplexNode *plist = NULL;
    ComplexNode *tmp1 = NULL;
    ComplexNode *tmp2 = NULL;
    PushBack(&plist, 1);
    PushBack(&plist, 2);
    PushBack(&plist, 3);
    PushBack(&plist, 4);
    PushBack(&plist, 5);

    tmp1 = FindComplexNode(plist, 3);
    plist->random = tmp1;
    tmp1->random = NULL;
    tmp1 = FindComplexNode(plist, 2);
    tmp1->random = plist;
    tmp1 = FindComplexNode(plist, 4);
    tmp2 = FindComplexNode(plist, 5);
    tmp1->random = tmp2;
    tmp2->random = tmp2;//初始化复杂链表
    LineComplexNode(plist);//第一步
    RandomEvaluate(plist);//第二步
    tmp1 = ToPickComplexList(plist);//摘出链表

    PrintComplexNode(plist);//打印原始链表
    PrintRandom(plist);//打印原始Random所指向数据

    PrintComplexNode(tmp1);//打印新链表
    PrintRandom(tmp1);//打印新random所指向数据
}

int main()
{
    Test();
    return 0;
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

结果：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/852705