7.判断俩个单向链表是否相交

long272449358

第7 题

微软亚院之编程判断俩个链表是否相交

给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。

为了简化问题，我们假设俩个链表均不带环。

问题扩展：

1.如果链表可能有环列?

2.如果需要求出俩个链表相交的第一个节点列?

#include <stdio.h>#include <stdlib.h>#include <conio.h>struct node {int value;node *next;};/** * 是否有环 */bool check(node* head) {if (head == NULL)return false;node *low = head, *fast = head -> next;while (fast != NULL && fast -> next != NULL) {low = low -> next;fast = fast -> next -> next;if(low == fast)return true;}return false;}/** * 获取尾结点 */node* lastNode(node* head) {if (head == NULL)return NULL;node* node = head;while (node -> next != NULL) {node = node -> next;}return node;}int main() {node *p1, *p2, *p2_2;p2_2 = (node*) malloc(sizeof(node));p2 -> value = 22;p2_2 -> next = NULL;p1 = (node*) malloc(sizeof(node));p1 -> value = 1;p1 -> next = p2_2;p2 = (node*) malloc(sizeof(node));p2 -> value = 2;p2 -> next = p2_2;if (check(p1) || check(p2)) {// 有环while (p1 != p2 && p1 != NULL && p2 != NULL) {p1 = p1->next;if (p2->next)p2 = p2->next->next;elsep2 = p2->next;}if (p1 == p2 && p1 && p2)printf("相交");elseprintf("不相交");} else {// 无环if (lastNode(p1) == lastNode(p2))printf("相交");elseprintf("不相交");}printf("\nPress any key to end");getch();return 0;}