本文主要是介绍Cracking The Coding Interview 2.5，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题的思想来自于http://hawstein.com/posts/2.5.html，重新实现了一下
用hash来记录循环的起点
//Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.//DEFINITION//Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.//EXAMPLE//Input: A -> B -> C -> D -> E -> C [the same C as earlier]#include <iostream>
#include <map>
using namespace std;typedef struct node{int data;node *next;
}node;node* init(int a[], int n, int m){node *head, *p, *q;for(int i=0; i<n; ++i){node *nd = new node();nd->data = a[i];if(i==m) q = nd;if(i==0){head = p = nd;continue;}p->next = nd;p = nd;}p->next = q;return head;
}map<node *, bool> st;
node * getLoopStart(node *head)
{node *p =head->next;while(p){if (st[p] != true){st[p] = true;p=p->next;}elsereturn p;}return p;
}int main(){int n = 10, m = 9;// m<nint a[] = {3, 2, 1, 3, 5, 6, 2, 6, 3, 1 };node *head = init(a, n, m);//node *p = loopstart(head);node *p2 = getLoopStart(head);if(p2)cout<<p2->data<<endl;return 0;
}
这篇关于Cracking The Coding Interview 2.5的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
