返回首页 一步一步写算法

链表重合

链表重合是一个好玩的问题。原题目是这样的:有两个链表,那么如何判断这两个链表是不是重合的?至于这个链表在什么时候重合的,这不重要,关键是判断这个链表究竟有没有重合。究竟有什么方法呢?

最简单的方法就是查看两者有没有共同点。那么依次判断就行了。

    int find_node_in_link(LINK_NODE* pLink, LINK_NODE* pNode)
    {
        while(pLink){
            if(pLink == pNode)
                return 1;
            pLink = pLink->next;
        }

        return 0;
    }

    STATUS find_if_link_merge(LINK_NODE* pLinkOne, LINK_NODE* pLinkTwo)
    {
        LINK_NODE* pHead;

        if(NULL == pLinkOne || NULL == pLinkTwo)
            return FALSE;

        pHead = pLinkTwo;
        while(pHead){
            if(find_node_in_link(pLinkOne, pHead))
                return TRUE;
            pHead = pHead->next;
        }

        return FALSE;
    }

另外一种方法就是计数的方法,既然链表在某处重合,那么此点访问的次数就是2,所以我们可以依次把两个链表遍历一下,最后查看有没有节点的count为2即可。

    typedef struct _LINK_NODE
    {
        int data;
        int count;
        struct _LINK_NODE* next;
    }LINK_NODE;

    void process_all_link_node(LINK_NODE* pNode)
    {
        assert(NULL != pNode);

        while(pNode){
            pNode->count ++;
            pNode = pNode->next;
        }
    }

从计数的方法,我们可以发现如果两个链表是重合的,那么他们的最后一个节点必然是相同的,所以只要判断最后一个节点是否相同即可。

    STATUS find_if_link_merge(LINK_NODE* pLinkOne, LINK_NODE* pLinkTwo)
    {
        assert(NULL != pLinkOne && NULL != pLinkTwo);

        while(pLinkOne->next) pLinkOne = pLinkOne->next;
        while(pLinkTwo->next) pLinkTwo = pLinkTwo->next;

        return (pLinkOne == pLinkTwo) ? TRUE : FALSE;
    }

总结:

(1)链表重合的题目虽然简单,但是从不同的角度可以有不同的答案;

(2)本题目来自《编程之美》, 如果对解法还有兴趣的朋友可以参考《编程之美》。