九 082010
面试题系列
大概的题意是，给出一个单向链表的头节点，求这么链表是否有环。有环的定义是，链表的尾节点指向了链接中间的某个节点。单链表的定义如下：
1 2 3 4 | struct Node { Node(): next(NULL) {} Node *next; }; |
这道题目还有一些变种，比如求链接的长度，求链表的尾节点等，不过大同小异。第一次听说这个题目，是在大三的时候，从一个刚面完试的学长那里。他当时的做法是对这个链表求逆，求逆的结果链表上每一个指针都反向，如果逆序完之后，链表的头节点不变，即说明链接有环。具体的证明过程略。这个方法的复杂也是O(N)，但是需要修改原链表，或者使用O(N)的额外空间。
标准做法是使用两个指针，一个每次往前走2步，一个每次往前走1步，如果两个指针相遇，即说明链表有环，时间复杂度为O(N)，空间复杂度为O(1)。
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | bool TestCircle(Node *p){ if (p == NULL){ return false; } if (p->next == NULL){ return false; } if (p->next == p){ return true; } Node *y = p->next; Node *x = p->next->next; while(x != NULL && y != NULL){ x = x->next; if (x == NULL) break; x = x->next; y = y->next; if (x == y) break; } return x == y; } |
测试数据也比较简单，考虑一下空指针、单个节点成环、整条链表成环就可以了：
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 | void RunTest(){ Node *p = NULL; Node *q = NULL; cout << "empty list" << endl; cout << TestCircle(NULL) << endl; cout << "one node not circle" << endl; p = new Node; cout << TestCircle(p) << endl; delete p; p = NULL; cout << "one node circle" << endl; p = new Node; p->next = p; cout << TestCircle(p) << endl; delete p; p = NULL; cout << "two nodes not circle" << endl; p = new Node; p->next = new Node; cout << TestCircle(p) << endl; delete p->next; delete p; p = NULL; cout << "two nodes circle" << endl; p = new Node; p->next = new Node; p->next->next = p; cout << TestCircle(p) << endl; delete p->next; delete p; p = NULL; cout << "two nodes circle case 2" << endl; p = new Node; p->next = new Node; p->next->next = p->next; cout << TestCircle(p) << endl; delete p->next; delete p; p = NULL; cout << "5 nodes not circle" << endl; p = new Node; q = p; for (int i = 0; i < 4; ++i){ q->next = new Node; q = q->next; } cout << TestCircle(p) << endl; while(p->next != NULL){ q = p->next->next; delete p->next; p->next = q; } delete p; p = NULL; cout << "5 nodes circle" << endl; p = new Node; q = p; for (int i = 0; i < 4; ++i){ q->next = new Node; q = q->next; } q->next = p; cout << TestCircle(p) << endl; q->next = NULL; while(p->next != NULL){ q = p->next->next; delete p->next; p->next = q; } delete p; p = NULL; cout << "5 nodes circle case 2" << endl; p = new Node; q = p; for (int i = 0; i < 4; ++i){ q->next = new Node; q = q->next; } q->next = p->next->next; cout << TestCircle(p) << endl; q->next = NULL; while(p->next != NULL){ q = p->next->next; delete p->next; p->next = q; } delete p; p = NULL; cout << "5 nodes circle case 3" << endl; p = new Node; q = p; for (int i = 0; i < 4; ++i){ q->next = new Node; q = q->next; } q->next = q; cout << TestCircle(p) << endl; q->next = NULL; while(p->next != NULL){ q = p->next->next; delete p->next; p->next = q; } delete p; p = NULL; cout << "100000000 nodes not circle" << endl; p = new Node; q = p; for (int i = 0; i < 100000000; ++i){ q->next = new Node; q = q->next; } cout << TestCircle(p) << endl; while(p->next != NULL){ q = p->next->next; delete p->next; p->next = q; } delete p; p = NULL; cout << "100000000 nodes circle" << endl; p = new Node; q = p; for (int i = 0; i < 100000000; ++i){ q->next = new Node; q = q->next; } q->next = p; cout << TestCircle(p) << endl; q->next = NULL; while(p->next != NULL){ q = p->next->next; delete p->next; p->next = q; } delete p; p = NULL; cout << "100000000 nodes circle case 2" << endl; p = new Node; q = p; for (int i = 0; i < 100000000; ++i){ q->next = new Node; q = q->next; } Node *t = p; for (int i = 0; i < 16; ++i){ t = t->next; } q->next = t; cout << TestCircle(p) << endl; q->next = NULL; while(p->next != NULL){ q = p->next->next; delete p->next; p->next = q; } delete p; p = NULL; } |
您还可能感兴趣的日志：