Point2OfferCode/23_EntryNode_List.cpp at master · slientreed/Point2OfferCode · GitHub

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

//
//  Created by mark on 2019/7/8.
//  Copyright © 2019年 mark. All rights reserved.
//

/*
 说明：
 1. 问题：23.找链表中环的入口节点
 2. 思路：判断是否有环；找到环中任一节点；计算环的个数；找到环的入口节点。
 */


#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <string>

using namespace std;

/*
 1. 如果有环，先找到环中任一节点： 双指针，快指针每次走两个节点，慢的走一个；如果快指针追上慢指针说明有环，且上的节点一定在环内；如果快指针到尾都没追上，没环
 2. 找到环中任一个节点，遍历一遍环，计算环的个数n；
 3. 定义两个指针，前面一个先走n步，然后后面跟前面一起走，相遇的节点就是环入口节点。
 */

struct ListNode
{
    int val;
    ListNode* next;
}LN,*pLN;


// 判断是否有环，有返回环中任一节点
ListNode* hasCycleList(ListNode* pHead)
{
    if(pHead == nullptr)
        return nullptr;

    ListNode* slow = pHead;

    ListNode* fast = pHead->next;

    while(fast != nullptr && slow != nullptr)
    {
        if(fast == slow)
            return fast;

        slow = slow->next;
        fast = fast->next;
        if(fast != nullptr)
            fast = fast->next;
    }

    return nullptr;
}


// 如果有环，计算链表环的长度
int LengthOfLoop(ListNode* node)
{
    int num = 0;
    //ListNode* p = hasCycleList(pHead);
    if(node == nullptr)
        return num;

    ListNode* cur = node->next;
    ++num;
    while(cur != node)
    {
        cur = cur->next;
        ++num;
    }

    return num;
}

// 求环的入口节点：两个指针，前指针先走环的长度步，后指针再走，两者相遇的就是入口节点
ListNode* EntryOfLoop(ListNode* pHead)
{
    ListNode* meeting = hasCycleList(pHead);
    int n = LengthOfLoop(meeting);
    if(n == 0)
        return nullptr;

    ListNode* first = pHead;
    ListNode* last = pHead;
    for(int i = 0; i < n; ++i)   // 先移动前面一个指针n步
    {
        first = first->next;
    }

    while(first != last)
    {
        first = first->next;
        last = last->next;
    }

    return last;
}


// ------------------------------------------------------------------------------------------------------------------------

// 辅助函数，创建链表
ListNode* CreatListNode(int val)
{
    ListNode* node = new ListNode();
    node->val = val;
    node->next = nullptr;

    return node;
}

// 辅助函数，连接两个链表节点
void ConnectListNodes(ListNode* pre, ListNode* cur)
{
    pre->next = cur;
}

// 遍历链表
void PrintList(ListNode* node)
{
    while(node != nullptr)
    {
        cout << node->val << " ";
        node = node->next;
    }
}


int main(){

    ListNode* p1 = CreatListNode(1);
    ListNode* p2 = CreatListNode(2);
    ListNode* p3 = CreatListNode(3);
    ListNode* p4 = CreatListNode(4);
    ListNode* p5 = CreatListNode(5);
    ListNode* p6 = CreatListNode(6);


    ConnectListNodes(p1, p2);
    ConnectListNodes(p2, p3);
    ConnectListNodes(p3, p4);
    ConnectListNodes(p4, p5);
    ConnectListNodes(p5, p6);
    ConnectListNodes(p6, p4);

    /*
    cout << "原链表是：";
    PrintList(p1);
    cout << endl;
    */

    ListNode* p = hasCycleList(p1);
    int n = LengthOfLoop(p);
    cout << "环的节点个数是：" << n << endl;

    ListNode* meet = EntryOfLoop(p1);
    cout << "环的入口节点是：" << meet->val << endl;


    return 0;
}