交叉链表

曾经终败给现在 2022-08-02 09:57 231阅读 0赞

两个单向链表，找出它们的第一个公共结点。链表的结点定义为：

struct ListNode

int  m\_nKey;

ListNode\*   m\_pNext;

\};

#include "stdafx.h"
    #include<stack>
    #include<iostream>
    
    using namespace std;
    
    struct ListNode
    {
    	int  m_nKey;
    	ListNode*   m_pNext;
    };
    
    
    
    ListNode*find_cross_node(ListNode*head1, ListNode*head2)
    {
    	ListNode*n1, *n2;
    	stack<int>a1, a2;
    	n1 = head1;
    	n2 = head2;
    	while (n1->m_pNext != NULL)
    	{
    		a1.push(n1->m_nKey);
    		n1 = n1->m_pNext;
    	}
    	while (n2->m_pNext != NULL)
    	{
    		a2.push(n2->m_nKey);
    		n2 = n2->m_pNext;
    	}
    	while (a1.top() == a2.top())
    	{
    		a1.pop();
    		a2.pop();
    		if (a1.empty())
    			break;
    		if (a2.empty())
    			break;
    	}
    
    	int k;
    	k = a2.size();
    	n2 = head2;
    	while (k)
    	{
    		n2 = n2->m_pNext;
    		k--;
    	}
    	k = a1.size();
    	n1 = head1;
    	while (k)
    	{
    		n1 = n1->m_pNext;
    		k--;
    	}
    	while (n1 != n2)
    	{
    		n1 = n1->m_pNext;
    		n2 = n2->m_pNext;
    	}
    	return n1;
    }
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	ListNode*head1 = new ListNode;
    	ListNode*head2 = new ListNode;
    	ListNode*node1 = new ListNode;
    	ListNode*node2 = new ListNode;
    	ListNode*node3 = new ListNode;
    	ListNode*node4 = new ListNode;
    	ListNode*node5 = new ListNode;
    	ListNode*node6 = new ListNode;
    	head1->m_nKey = 0;
    	head2->m_nKey = 0;
    	node1->m_nKey = 0;
    	node2->m_nKey = 0;
    	node3->m_nKey = 0;
    	node4->m_nKey = 4;
    	node5->m_nKey = 5;
    	node6->m_nKey = 6;
    
    	head1->m_pNext = node1;
    	node1->m_pNext = node2;
    	head2->m_pNext = node3;
    	node3->m_pNext = node4;
    	node2->m_pNext = node4;
    	node4->m_pNext = node5;
    	node5->m_pNext = node6;
    	node6->m_pNext = NULL;
    
    
    	ListNode*cross_node = find_cross_node(head1, head2);
    	if (cross_node == NULL)
    		cout << "两个链表不交叉" << endl;
    
    	system("pause");
    	return 0;
    }

思路是：从两个链表交叉点开始，后面的都重合，因此很自然将两个链表末尾对齐，对齐方法是从后往前一个节点一个节点的比较值，若不相等，则从这两个链表不相等位置的下一个开始一一比较就行了。

复杂度应该是O(n)。