算法题之---《链表相交》

首先，我们要知道链表相交意味着什么？

根据链表的特质，只要两个链表相交，也就是说他们有共同的节点，那么从共同的节点往后的所有节点都是相同的

接下来，怎么证明两个链表相交呢？以及怎么获取他们的第一个交点？

首先，我们根据链表相交的结果，很容易想到的是直接判断两个链表的最后一个节点是相同，因为链表相交的话，他们最后的节点必定是相同的。那么判断相交就变成了判断尾节点是否相同了，这里就有很多种方法了，比如，最简单的，机智的我一开始就保留了head节点和foot尾节点，直接拿来比一比就行了；再比如，啥也别说了，就是干，一个一个遍历，遍到头就行了；

下面呢，我们就用最直观的办法，借助栈，将链表元素从head一个一个入栈，到最后，栈顶元素就是尾节点了，只要比较两个栈的栈顶节点就可以了：

链表相交

下面是简单的示例代码：

-(ListNode *)crossWithList:(List *)list {
    
    // 1. 将两个链表入栈，这里用数组表示栈
    NSMutableArray *queue1 = [NSMutableArray array];
    NSMutableArray *queue2 = [NSMutableArray array];
    
    ListNode *currentNodeOfSelf = self.head;
    while (currentNodeOfSelf != nil) {
        [queue1 insertObject:currentNodeOfSelf atIndex:0];
        currentNodeOfSelf = currentNodeOfSelf.next;
    }
    
    ListNode *currentNodeOfList = list.head;
    while (currentNodeOfList != nil) {
        [queue2 insertObject:currentNodeOfList atIndex:0];
        currentNodeOfList = currentNodeOfList.next;
    }
    
    // 栈顶节点相同则相交，否则不相交
    if (queue1[0] == queue2[0]) {
        
        ListNode *lastCommonNode = queue1[0]; // 用来保存最后一个相同的节点，就是他们的交点
        NSInteger minCount = MIN(queue1.count, queue2.count);
        NSInteger i=0;
        
        for (; i<minCount; i++) {
            if (queue1[i] == queue2[i]) {
                lastCommonNode = queue1[i];
            } else {
                return lastCommonNode;
            }
        }
        return queue1[i];
        
    } else {
        return nil;
    }
}

最后还有一种方法，如果不考虑时间复杂度的话，也可以用两层循环，分别遍历两个链表，并逐个逐个的比较，第一个相同的节点就是交点。