剑指offer之面试题37两个链表的第一个公共结点

男娘i 2022-07-24 04:04 153阅读 0赞

**问题描述**：

输入两个链表，找出他们的第一个公共结点。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    typedef struct Node Node;
    struct Node{
    	int value;
    	Node *next;
    };
    
    int getLenList(Node *root){
    	int len=0;
    	if(root==NULL){
    		return len;
    	}
    	while(root!=NULL){
    		len++;
    		root=root->next;
    	}
    	return len;
    }
    
    
    Node *findFirstCommonNode(Node *root1,Node *root2){
    	int root1Len = getLenList(root1);
    	int root2Len =getLenList(root2);
    	Node *longList=root1;
    	Node *shortList=root2;
    	int LsubS=root1Len-root2Len;
    	if(root1Len<root2Len){
    		longList=root2;
    		shortList=root1;
    		LsubS=root2Len-root1Len;
    	}
    	while(LsubS--){
    		longList=longList->next;
    	}
    	while(longList!=NULL && shortList!=NULL && longList!=shortList){
    		longList=longList->next;
    		shortList=shortList->next;
    	}
    	Node *rs =longList;
    	return rs;
    }
    int main(int argc, char *argv[])
    {
    	Node *root1 = (Node *)malloc(sizeof(Node));root1->value=1;
    	Node *root2 = (Node *)malloc(sizeof(Node));root2->value=2;
    	Node *root3 = (Node *)malloc(sizeof(Node));root3->value=3;
    	Node *root4 = (Node *)malloc(sizeof(Node));root4->value=4;
    	root1->next=root3;
    	root3->next=root4;
    	root2->next=root4;
    	root4->next=NULL;
    	
    	Node *rs = findFirstCommonNode(root1,root2);
    	printf("%d\n",rs->value);
    	return 0;
    }

上面算法的时间复杂度是O(m+n)，空间复杂度是O(1)。

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51336078  
作者：WSYW126