- 论坛徽章:
- 0
|
本帖最后由 hp_truth 于 2010-08-04 18:15 编辑
大家都是牛人, 让新人受益良多。
今天看到关于单向链表的这个两个帖子, 觉得很有收获, 自己参考各位的想法写了一个小程序, 以后得多向各位学习。
按照版主的想法, 大体思路是: 在判断是否有环路时, 我们可以得到相遇的节点, 计为M。 然后我们可以从头部节点H开始遍历,直到这个遇到M, 这个距离算作i; 我们也可以计算从M节点开始,绕环再走一圈(重新回到M)的距离, 计为j。
然后让指针P1指向H, P2指向M, 如果i>j, 则让P1先往前走(i-j)步; 如果j>i,则让P2往前走(j-i)步.
接下来, P1和P2 同时往前走, 它们必然相遇于环的第一个节点.
- #include <stdio.h>
- #include <stdlib.h>
- struct list {
- int data;
- struct list * next;
- };
- // judge if the list has a loop
- int has_loop (struct list *head, struct list **meeting_node) {
- int step1 = 1, step2 = 2;
- struct list *p1 = head, *p2 = head;
- int i;
- while ( p1 != NULL ) {
- for (i=0; i!=step1; ++i) {
- p1 = p1->next;
- }
- for (i=0; i!=step2; ++i) {
- p2 = p2->next;
- if (p2 == NULL)
- return 0;
- }
- printf ("p1->data = %d, p2->data = %d\n", p1->data, p2->data);
- if ( p1 != NULL && p1 == p2 ) {
- *meeting_node = p1;
- return 1;
- }
- }
- return 0;
- }
- struct list * first_node_of_loop(struct list *h) {
- struct list *meeting_node = NULL;
- struct list *p1 = h, *p2 = h;
- int i, j, k;
- if (!has_loop(h, &meeting_node)) {
- return NULL;
- }
- printf("meeting_node: %d\n", meeting_node->data);
- // how long from head node to meeting_node
- i = 0;
- while (p1 != meeting_node) {
- ++i;
- p1 = p1->next;
- }
- // how long of the loop
- j = 1;
- p2 = meeting_node->next;
- while (p2 != meeting_node) {
- ++j;
- p2 = p2->next;
- }
- printf("i=%d, j=%d\n", i,j);
- // let them start at the same distance away from meeting_node
- p1 = h;
- p2 = meeting_node;
- if (i > j) {
- k = i - j;
- while(k-- > 0) {
- p1 = p1->next;
- }
- }
- else {
- k = j - i;
- while(k-- > 0) {
- p2 = p2->next;
- }
- }
- // now they are at the same distance away from meeting_node,
- // let them move on until they meet at the initial_node_of_loop
- while (p1 != p2) {
- p1 = p1->next;
- p2 = p2->next;
- }
- return p1;
- }
- void print_list (struct list *h) {
- int cnt = 0;
- int max_step = 25;
- while ( h != NULL ) {
- printf("%d ", h->data);
- h = h->next;
- // to prevent infinite loop
- if (++cnt > max_step) {
- printf("\n");
- return;
- }
- }
- printf("\n");
- }
- // add a new node to the existing list
- void add_to_list(struct list ** ph, int d) {
- struct list *p = malloc(sizeof(struct list));
- if (p == NULL) {
- printf("malloc failed\n");
- abort();
- }
- p->data = d;
- p->next = NULL;
- if ( *ph == NULL ) {
- *ph = p;
- return;
- }
- struct list *h = *ph;
- while ( h->next != NULL) {
- h = h->next;
- }
- h->next = p;
- }
- // let the tailer of the list point to the nth node
- void create_loop (struct list *h, int n) {
- struct list *p = h;
- struct list *n_node = h;
- int i = 1;
- while ( p->next != NULL ) {
- p = p->next;
- if (++i == n) {
- n_node = p;
- }
- }
- p->next = n_node;
- }
- int main ( int argc, char *argv[] )
- {
- // create a list
- struct list *head = NULL;
- struct list *meeting_node = NULL;
- int i;
- for (i=1; i!=10; ++i)
- add_to_list(&head, i);
- print_list(head);
- if (has_loop(head, &meeting_node)) {
- printf("has loop at node: %d\n", meeting_node->data);
- }
- else {
- printf("has no loop\n");
- }
- // create a loop in the list
- create_loop(head, 2);
- print_list(head);
- if (has_loop(head, &meeting_node)) {
- printf("has loop at node: %d\n", meeting_node->data);
- }
- else {
- printf("has no loop\n");
- }
- struct list *first_node = first_node_of_loop(head);
- if (first_node) {
- printf("the first node of loop is: %d\n", first_node->data);
- }
- return 0;
- }
复制代码 |
|