判断两条链表是否交叉,若有交叉,返回交叉节点的指针。
英语文化交流 > 技术博客 > 判断两条链表是否交叉,若有交叉,返回交叉节点的指针。
判断两条链表是否交叉,若有交叉,返回交叉节点的指针。
时间: 分类:技术博客

上周面试挂了,反思原因,莫非是因为一道算法题没做好吗?这题目是“判断两条链表是否交叉,若有交叉,返回交叉节点的指针。” 为了防止反复在同一个阴沟里翻船,决定把最优解写出来。

#include "pch.h"
#include <iostream>
#include<assert.h>

template<typename T>
class List {
public:
    struct Node {
        T data;
        Node* next = nullptr;
        Node(T& d) : data(d) {}
    };
    Node* m_head = nullptr;
private:
    enum {
        E_SUCCESS = 0,
        E_FAIL = -1
    };
public:
    //List(){}
    ~List() 
    {
        Node* pcur = m_head, *pnext = nullptr;
        while (pcur) {
            pnext = pcur->next;
            delete pcur;
            pcur = pnext;
        }
    }
    int AddNode(T dt, bool at_tail = true) 
    {
        Node*ptr = new Node(dt);
        return AddNode(ptr, at_tail);
    }
    int AddNode(Node* nd, bool at_tail = true) 
    {
        if (nd) {
            if (at_tail) {
                Node* ptail = Tail();
                if (ptail) {
                    ptail->next = nd;
                }
                else {
                    m_head = nd;
                }
            }
            else {
                nd->next = m_head;
                m_head = nd;
            }
            return E_SUCCESS;
        }
        return E_FAIL;
    }

    Node* Intersect(List& oth) 
    {
        Node* entrance1 = LoopEntrance();
        Node* entrance2 = oth.LoopEntrance();
        if (entrance1 == entrance2) {
            return entrance1;
        }
        else if (!entrance1 && !entrance2) {
            Node* longlist_ptr = nullptr, *shortlist_ptr = nullptr;
            {
                const int sz1 = Size();
                const int sz2 = oth.Size();
                int num = 0;
                if (sz1 >= sz2) {
                    longlist_ptr = m_head;
                    shortlist_ptr = oth.m_head;
                    num = sz1 - sz2;
                }
                else {
                    longlist_ptr = oth.m_head;
                    shortlist_ptr = m_head;
                    num = sz2 - sz1;
                }
                for (int i = 0; i < num; ++i) {
                    if (longlist_ptr) {
                        longlist_ptr = longlist_ptr->next;
                    }
                }
            }
            while (longlist_ptr && shortlist_ptr) {
                if (longlist_ptr == shortlist_ptr) {
                    return longlist_ptr;
                }
                longlist_ptr = longlist_ptr->next;
                shortlist_ptr = shortlist_ptr->next;
            }
        }
        return nullptr;
    }

    Node* LoopEntrance() {
        Node *fast_ptr = m_head, *slow_ptr = m_head;
        bool has_loop = false;
        while (fast_ptr && fast_ptr->next) {
            fast_ptr = fast_ptr->next->next;
            slow_ptr = slow_ptr->next;
            if (fast_ptr == slow_ptr) {
                has_loop = true;
                break;
            }
        }
        if (has_loop) {
            slow_ptr = m_head;
            while (1 /*fast_ptr && fast_ptr->next && slow_ptr*/) {
                if (fast_ptr == slow_ptr) {
                    return fast_ptr;
                }
                fast_ptr = fast_ptr->next;
                slow_ptr = slow_ptr->next;
            }
        }
        return nullptr;
    }

private:
    Node* Tail() {
        if (LoopEntrance()) {
            return nullptr;
        }
        Node* ptr = m_head;
        while (ptr && ptr->next) {
            ptr = ptr->next;
        }
        return ptr;
    }
    int Size() 
    {
        int sz = 0;
        Node* ptr = m_head;
        Node* entrance = LoopEntrance();
        if (entrance) {
            while (ptr && ptr != entrance) {
                sz++;
                ptr = ptr->next;
            }
            assert(ptr == entrance);
            sz++; // entrance point
            while (ptr && ptr->next != entrance) {
                sz++;
                ptr = ptr->next;
            }
        }
        else {
            while (ptr) {
                sz++;
                ptr = ptr->next;
            }
        }
        return sz;
    }
};

int main()
{
    std::cout << "Hello World!\n"; 
    List<int> list1, list2;
    for (int i = 1; i < 3; ++i) {
        list1.AddNode(i);
    }
    for (int i = 25; i < 28; ++i) {
        list2.AddNode(i);
    }

#if 1
    for (int i = 100; i < 101; ++i) {
        List<int>::Node* node = new List<int>::Node(i);
        list1.AddNode(node);
        list2.AddNode(node);
    }
#endif
    auto ptr = list1.Intersect(list2);
    if (ptr) {
        std::cout << "intersect point at " << ptr << std::endl;
    }
    else {
        std::cout << "no intersect\n";
    }

    return 0;
}

代码创建了两条有交叉节点的链表。如图所示:
判断两条链表是否交叉,若有交叉,返回交叉节点的指针。

程序运行结束时,析构这两条链表,发生错误,是因为交叉节点被两次释放:
判断两条链表是否交叉,若有交叉,返回交叉节点的指针。

随机阅读

Copyright © 2017 英语文化交流 All Rights Reserved.