题目：

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

链表 结点定义:

.h文件

#import <Foundation/Foundation.h>
// 链表 节点
@interface NSListNode : NSObject
// value
@property (nonatomic, assign) NSInteger value;
// next
@property (nonatomic, strong) NSListNode *next;
// 生成 NSListNode
+ (NSListNode *)configWithValue:(NSInteger)value;
@end

.m文件

#import "NSListNode.h"

@implementation NSListNode
#pragma mark --------------- Public Methods
// 生成 NSListNode
+ (NSListNode *)configWithValue:(NSInteger)value {
    NSListNode *tmpNode = [[NSListNode alloc] init];
    tmpNode.value = value;
    return tmpNode;
}
@end

解题思路：

第一种：直接法
　　在第一个链表上顺序遍历每个结点，每遍历到一个结点的时候，在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和第一个链表上的结点一样，说明两个链表在这个结点上重合，于是就找到了它们的公共结点。如果第一个链表的长度为m，第二个链表的长度为n，显然该方法的时间复杂度是O(mn） 。

第二种：使用栈
　　所以两个有公共结点而部分重舍的链衰，拓扑形状看起来像一个Y， 而不可能像X（如图5.3 所示）。

这里写图片描述

经过分析我们发现，如果两个链表有公共结点，那么公共结点出现在两个链表的尾部。如果我们从两个链衰的尾部开始往前比较，最后一个相同的结点就是我们要找的结点。
　　在上述思路中，我们需要用两个辅助栈。如果链表的长度分别为m 和n，那么空间复杂度是O(m+n）。这种思路的时间复杂度也是O(m+n）。和最开始的蛮力法相比，时间效率得到了提高，相当于是用空间消耗换取了时间效率。

第三种：先行法
　　在图5.3 的两个链表中，我们可以先遍历一次得到它们的长度分别为5和4， 也就是较长的链表与较短的链表相比多一个结点。第二次先在长的链表上走1 步，到达结点2。接下来分别从结点2 和结点4 出发同时遍历两个结点， 直到找到它们第一个相同的结点6，这就是我们想要的结果。
　　第三种思路和第二种思路相比，时间复杂度都是O(m＋n + (m和n最大值))， 但我们不再需要辅助的控件，因此提高了空间效率。

实现代码:

#import "NSListNode.h"
#import "NSCustomStack.h"
#import <Foundation/Foundation.h>


/**
 找到 两个 链表 的第一个 公共 节点

 @param firstHeaderNode 第一条 链表 头结点
 @param secondHeaderNode 第二条 链表 头结点
 @return 返回 第一个 公共 结点
 */
NSListNode *findFirstCommonNodeOne(NSListNode *firstHeaderNode, NSListNode *secondHeaderNode) {
    if (firstHeaderNode == nil || secondHeaderNode == nil) {
        return nil;
    }
    
    // 初始化 存储链表 值的栈
    NSCustomStack *firstCustomStack = [[NSCustomStack alloc] init];
    NSCustomStack *secondCustomStack = [[NSCustomStack alloc] init];
    while (firstHeaderNode != nil) {
        [firstCustomStack push:firstHeaderNode];
        firstHeaderNode = firstHeaderNode.next;
    }
    
    while (secondHeaderNode != nil) {
        [secondCustomStack push:secondHeaderNode];
        secondHeaderNode = secondHeaderNode.next;
    }
    
    // 比较 栈值
    NSListNode *tmpFirstNode = [firstCustomStack popTopElement];
    NSListNode *tmpSecondNode = [secondCustomStack popTopElement];
    while (tmpFirstNode.value == tmpSecondNode.value) {
        tmpFirstNode = [firstCustomStack popTopElement];
        tmpSecondNode = [secondCustomStack popTopElement];
    }
    return tmpFirstNode.next;
}

/**
 找到 两个 链表 的第一个 公共 节点
 
 @param firstHeaderNode 第一条 链表 头结点
 @param secondHeaderNode 第二条 链表 头结点
 @return 返回 第一个 公共 结点
 */
NSListNode *findFirstCommonNodeTwo(NSListNode *firstHeaderNode, NSListNode *secondHeaderNode) {
    if (firstHeaderNode == nil || secondHeaderNode == nil) {
        return nil;
    }
    
    int firstListNodeLength = 0;
    int secondListNodeLength = 0;
    NSListNode *currentFirstHeaderNode = firstHeaderNode;
    NSListNode *currentSecondHeaderNode = secondHeaderNode;
    
    while (currentFirstHeaderNode != nil) {
        firstListNodeLength ++;
        currentFirstHeaderNode = currentFirstHeaderNode.next;
    }
    
    while (currentSecondHeaderNode != nil) {
        secondListNodeLength ++;
        currentSecondHeaderNode = currentSecondHeaderNode.next;
    }
    
    int listNodeSpacing = abs(firstListNodeLength - secondListNodeLength);
    if(firstListNodeLength > secondListNodeLength) {
        for(int tmpIndex = 0; tmpIndex < listNodeSpacing; tmpIndex ++) {
            firstHeaderNode = firstHeaderNode.next;
        }
    }
    else if(firstListNodeLength < secondListNodeLength){
        for(int tmpIndex = 0; tmpIndex < listNodeSpacing; tmpIndex ++) {
            secondHeaderNode = secondHeaderNode.next;
        }
    }
    
    while (firstHeaderNode != nil) {
        if (firstHeaderNode.value == secondHeaderNode.value) {
            break;
        }
        firstHeaderNode = firstHeaderNode.next;
        secondHeaderNode = secondHeaderNode.next;
    }
    return firstHeaderNode;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSListNode *firstNode = [NSListNode configWithValue:0];
        NSListNode *secondNode = [NSListNode configWithValue:1];
        
        NSListNode *node2 =[NSListNode configWithValue:2];
        NSListNode *node3 = [NSListNode configWithValue:3];
        NSListNode *node4 = [NSListNode configWithValue:4];
        NSListNode *node5 = [NSListNode configWithValue:5];
        NSListNode *node6 = [NSListNode configWithValue:6];
        NSListNode *node7 = [NSListNode configWithValue:7];
        
        firstNode.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = nil;
        
        secondNode.next = node2;
        

        printf("%ld ", (long)findFirstCommonNodeTwo(firstNode, secondNode).value);

    }
    return 0;
}