研发埠

标题: 微软亚院之编程判断俩个链表是否相交 [打印本页]

作者: 王鹏 时间: 2013-8-16 10:36
标题: 微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?

作者: 陈荣莲 时间: 2013-8-16 10:45
structNode { int data; int Node *next;};// if there is no cycle.int isJoinedSimple(Node * h1, Node * h2) { while (h1->next != NULL) { h1 = h1->next; } while (h2->next != NULL) { h2 = h2-> next; } return h1 == h2;}// ifthere could exist cycleint isJoined(Node *h1, Node * h2) { Node* cylic1 = testCylic(h1); Node* cylic2 = testCylic(h2); if (cylic1+cylic2==0) return isJoinedSimple(h1, h2); if (cylic1==0 && cylic2!=0 || cylic1!=0 &&cylic2==0)return 0; Node *p = cylic1; while (1) { if (p==cylic2 || p->next == cylic2) return 1; p=p->next->next; cylic1 = cylic1->next; if (p==cylic1) return 0; }}Node*testCylic(Node * h1) { Node * p1 = h1, *p2 = h1; while (p2!=NULL && p2->next!=NULL) { p1 = p1->next; p2 = p2->next->next; if (p1 == p2) { return p1; } } return NULL;}

欢迎光临研发埠 (http://bbs.yanfabu.com/)