每日一练——两个单链表相交的一系列问题

题意描述：
单链表可能有环，也可能无环。给定两个单链表的头节点head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null。
要求：

如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N+M)，额外空间复杂度请达到O(1)。

结构体如下：

struct node
{
        node(int val) : value(val), next(NULL){}
        int value;
        struct node *next;
};

每日一练——两个单链表相交的一系列问题

struct node *get_first_same_node(stack<struct node *> &stk1, stack<struct node *> &stk2)
{
    struct node *intersect_node = NULL;
    while (stk1.size() && stk2.size() && stk1.top() == stk2.top())
    {
        intersect_node = stk1.top();
        stk1.pop();
        stk2.pop();
    }

    return intersect_node;
}

struct node *no_loop(struct node *&head1, struct node *&head2)
{
    stack<struct node *> stk1, stk2;
    struct node *cur_node;

    cur_node = head1;
    while (cur_node)
    {
        stk1.push(cur_node);
        cur_node = cur_node->next;
    }

    cur_node = head2;
    while (cur_node)
    {
        stk2.push(cur_node);
        cur_node = cur_node->next;
    }

    return get_first_same_node(stk1, stk2);
}

每日一练——两个单链表相交的一系列问题

struct node *both_loop(struct node *&head1, struct node *&loop1,
                       struct node *&head2, struct node *&loop2)
{
    //在进环前相交
    if (loop1 == loop2)
    {
        stack<struct node *> stk1, stk2;
        struct node *cur_node;

        cur_node = head1;
        while (cur_node != loop1)
        {
            stk1.push(cur_node);
            cur_node = cur_node->next;
        }

        cur_node = head2;
        while (cur_node != loop2)
        {
            stk2.push(cur_node);
            cur_node = cur_node->next;
        }

        return get_first_same_node(stk1, stk2);//找到第一个相同的节点
    }
    //在进环后相交
    else
    {
        return loop1;//or return loop2
    }
}

如何找出带环路的链表的第一个进环的节点？
假设进环前链表的长度为L，环形链表的长度是S，使用快慢指针，快的指针一次走两步，慢的指针一次走一步，那么他们必然在环路上相遇，假设相遇的节点离进环节点的距离是X，那么必然有L + S + X = 2 * ( L + X)，可以推出S = L + X, 从而推出L = S - X。重新将一个指针指向头节点，然后和之前的慢指针（从环路相遇点开始）以相同的速度向前走。最后必然会在进环节点处相遇。

每日一练——两个单链表相交的一系列问题

//获取第一个进环的节点struct node *get_in_loop_node(struct node *&head)
{
    if (head == NULL || head->next == NULL)
    {
        return NULL;
    }
    struct node *fast_node , *slow_node;
    slow_node = head->next;
    fast_node = head->next->next;

    while (slow_node != fast_node)
    {
        if (fast_node->next == NULL || fast_node->next->next == NULL)
        {
            return NULL;
        }

        fast_node = fast_node->next->next;
        slow_node = slow_node->next;
    }

    struct node *in_loop_node = head;

    while (in_loop_node != slow_node)
    {
        in_loop_node = in_loop_node->next;
        slow_node = slow_node->next;
    }

    return in_loop_node;
}

综合以上几种情况，我们可以知道，如果两个链表都没有环路，那么用栈来处理；如果两个链表都有环路，但是在进环的节点一样，那么说明它们在进环前就相交，和第一种情况一样处理；如果两个链表都有环路，但是进环节点不一样，那么一定是在进环后相交，进环的两个节点均可认为是相交的节点；如果一个链表有环一个链表无环，那么这两个链表一定不会相交。


struct node * get_intersect_node(struct node *&head1, struct node *&head2)
{
    if (head1 == NULL ||head2 == NULL)
    {
        return NULL;
    }

    struct node *loop1 = get_in_loop_node(head1);
    struct node *loop2 = get_in_loop_node(head2);

    //两个链表均无环路
    if (loop1 == NULL && loop2 == NULL)
    {
        return no_loop(head1, head2);
    }

    //两个链表均有环路
    if (loop1 != NULL && loop2 != NULL)
    {
        return both_loop(head1, loop1, head2, loop2);
    }
    //一个链表有环路，一个链表没有环路，必然不相交
    return NULL;
}

参考：

http://www.nowcoder.com/live/11/6/live

秒客网

每日一练——两个单链表相交的一系列问题

相关文章