两个单链表相交问题2——无环链表相交

题目：如何判断两个无环链表相交，相交则返回第一个相交的节点，否则直接返回NULL
解题步骤：
（1）链表1从头节点开始遍历到最后一个节点，记录最后一个节点end1和遍历的长度len1
（2）链表2从头节点开始遍历到最后一个节点，记录最后一个节点end2和遍历的长度len2
（3）如果end1 != end2则说明两个链表不相交，返回NULL。如果end1 == end2，则说明有交点
（4）如果len1大于len2，链表1的指针先走len1-len2步。否则len2大于len1，则链表2的指针先走len2-len1步。之后二者一起走，两个链表第一次走到一起时就是相交的节点

代码：

#include<bits/stdc++.h>
using namespace std;

typedef struct node
{
   int val;
   struct node* next;
}node;


node* head_insert(node *L, int n){
	if(n <= 0){
		printf("num is error\n");
		return NULL;
	}
	node* input = NULL; 
    for(int i = n; i >= 1; i--)
    {
        node* new_node = (node*)malloc(sizeof(node));
        new_node->val = i;
        new_node->next = NULL;
        if(i == 6){
        	input = new_node;
		}
        new_node -> next = L -> next;
        L -> next = new_node;
    }
    return input;
}

void CreateList2(node* L, node* input, int n){
	if(n <= 0){
		printf("num is error\n");
		return;
	}
	
	for(int i = n; i >= 1; i--){
		node* new_node = (node*)malloc(sizeof(node));
		new_node->val =  i;
		new_node->next = input;
		input = new_node;
		L->next = input;
	}
}

node* NoLoop_input(node* head1, node* head2){
	if(head1 == NULL || head2 == NULL){
		return NULL;
	}
	node* p1 = head1->next;
	node* p2 = head2->next;
	int len = 0;
	while(p1){
		len++;
		p1 = p1->next;
	}
	while(p2){
		len--;
		p2 = p2->next;
	}
	if(p1 != p2){
		return NULL;
	}
	p1 = len > 0 ? head1 : head2;
	p2 = (p1 == head1) ? head2 : head1;
	len = abs(len);
	while(len!=0){
		len--;
		p1 = p1->next;
	}
	while(p1 != p2){
		p1 = p1->next;
		p2 = p2->next;
	}
	return p1;
}

void Print(node *L){
    node *p = L->next;
    if(p == NULL){
    	printf("L is NULL\n");
    	return;
	} 
	else{
        printf("%d",p->val);
        p = p->next;
    }
    while(p){
        printf("->%d",p->val);
        p = p->next;
    }
    puts("");
}

int GetLen(node* head){
	
	node* p = head->next;
	int len = 0;
	while(p){
		len++;
		p = p->next;
	}
	return len;
}

int main()
{
    int n; 
    node* L1 =(node*) malloc(sizeof(node));
	L1->next = NULL;
	node* L2 = (node*) malloc(sizeof(node));
	L2->next = NULL;
	node* input = NULL;
    node* ans = NULL;
	//------------------head_insert------------------//
    printf("Please Input L1's Insert nums:");
    scanf("%d",&n);
   	input = head_insert(L1,n);
    Print(L1);
    cout<<"L1's len is "<<GetLen(L1)<<endl;
    puts(""); 
    //-----------------------------------------------//
	printf("Please Input L2's Insert nums:");
    scanf("%d",&n);
    CreateList2(L2,input,n);
  	Print(L2);
  	cout<<"L2's len is "<<GetLen(L2)<<endl;
  	puts(""); 
  	//-----------------------------------------------//
  	ans = NoLoop_input(L1,L2);
  	if(ans){
  		printf("enter node's val is %d\n",ans->val);	
	}
	else {
		printf("NO enter\n");
	}
    return 0;
}

结果：
两个单链表相交问题2——无环链表相交

两个单链表相交问题2——无环链表相交

相关推荐