数据结构与算法-链表

链表

一、判断两个单链表是否相交及找到第一个交点

如果两个单链表有共同的节点，那么从第一个共同节点开始，后面的节点都会重叠，直到链表结束。因为两个链表中有一个共同节点，则这个节点里的指针域指向的下一个节点地址一样，所以下一个节点也会相交，依次类推。所以，若相交，则两个链表呈“Y”字形。

1. 使用栈
   可以从头遍历两个链表。创建两个栈，第一个栈存储第一个链表的节点，第二个栈存储第二个链表的节点。每遍历到一个节点时，就将该节点入栈。两个链表都入栈结束后。则通过 top 判断栈顶的节点是否相等即可判断两个单链表是否相交。因为我们知道，若两个链表相交，则从第一个相交节点开始，后面的节点都相交。若两链表相交，则循环出栈，直到遇到两个出栈的节点不相同，则这个节点的后一个节点就是第一个相交的节点。

   node temp = NULL;   // 存第一个相交节点
   
   while(!stack1.empty() && !stack2.empty())   // 两栈都不为空
   {
       temp = stack1.pop();
       stack1.pop();
       stack2.pop();
       if(stack1.top() != stack2.top())
       {
           break;
       }
   }

2. 遍历链表记录长度
   同时遍历两个链表到尾部，记录两个链表的长度。若两个链表最后的一个节点相同，则两个链表相交。有两个链表的长度后，我们就可以知道哪个链表长，设较长的链表长度为 len1，较短的链表长度为 len2。则先让较长的链表向后移动 (len1-len2) 个长度。然后开始从当前位置同时遍历两个链表，当遍历到的链表的节点相同时，则这个节点就是第一个相交的节点。

   struct ListNode
   {
       int val;
       struct ListNode* next;
       ListNode(int x) : val(x), next(NULL) {}
   };
   
   // 找出第一个相同的节点
   ListNode* findFirstNode(ListNode* l1, ListNode* l2)
   {
       if(l1 == NULL || l2 == NULL)
       {
           return NULL;
       }
       ListNode* p1, p2;
       p1 = l1;
       p2 = l2;
       int len1 = 0;
       int len2 = 0;
       int diff = 0;
       while(p1->next != NULL)
       {
           p1 = p1->next;
           len1++;
       }
       while(p2->next != NULL)
       {
           p2 = p2->next;
           len2++;
       }
       if(p1 != p2)
       {
           return NULL;    // 如果最后一个节点不相同，返回 NULL
       }
       diff = abs(len1 - len2);
       // 两个移动指针重新变换指向，p1 总是指向较长的链表头，p2 总是指向较短的链表
       if(len1 > len2)
       {
           p1 = l1;
           p2 = l2;
       }
       else
       {
           p1 = l2;
           p2 = l1;
       }
       for(int i = 0; i < diff; i++)
       {
           p1 = p1->next;
       }
       while(p1 != p2)
       {
           p1 = p1->next;
           p2 = p2->next;
       }
       return p1;
   }
   
   // 指向较长链表的指针先移动 diff 距离，因为多出的部分肯定是在第一个相同节点的前面。

3. 哈希表法
   既然两个个链表一旦相交，相交节点一定有相同的内存地址，而不同的节点内存地址一定是不同的，那么不妨利用内存地址建立哈希表，如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是：遍历第一个链表，并利用地址建立哈希表，遍历第二个链表，看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。
   可以采用除留取余法构造哈希函数。构造哈希表可以采用链地址法解决冲突。哈希表冲突指对 key1 != key2，存在 f(key1) = f(key2)，链地址法就是把 key1 和 key2 作为节点放在同一个单链表中，这种表称为同义词子表，在哈希表中只存储同义词子表的头指针。

二、链表中环的入口结点

如果链表中环有 n 个结点，指针 P1 在链表上向前移动 n 步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈又回到了入口结点。所以首先要得到环中结点的数目。

Java 版

public class 链表中环的入口结点 {
    //找到一快一慢指针相遇处的节点，相遇的节点一定是在环中
    public static ListNode meetingNode(ListNode head) {
        if(head==null)
            return null;
         
        ListNode slow = head.next;
        if(slow==null)
            return null;
         
        ListNode fast = slow.next;
        while (slow != null && fast != null) {
            if(slow==fast){
                return fast;
            }
            slow=slow.next;
            fast=fast.next;
            /* 有问题的？
            if(fast!=slow){
                fast=fast.next;
            }
            */
        }
        return null;
    }
    
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode meetingNode=meetingNode(pHead);
        if(meetingNode==null)
            return null;
//      得到环中的节点个数
        int nodesInLoop=1;
        ListNode p1=meetingNode;
        while(p1.next!=meetingNode){
            p1=p1.next;
            ++nodesInLoop;
        }
//      移动p1
        p1=pHead;
        for(int i=0;i<nodesInLoop;i++){
            p1=p1.next;
        }
//      移动p1，p2
        ListNode p2=pHead;
        while(p1!=p2){
            p1=p1.next;
            p2=p2.next;
        }
        return p1;
    }
}

C++ 版

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
 
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead==NULL || pHead->next==NULL)
            return NULL;
 
        ListNode* pSlow=pHead;
        ListNode* pFast=pHead;
        // detect if the linklist is a circle
        while(pFast!=NULL && pFast->next!=NULL){
            pSlow=pSlow->next;
            pFast=pFast->next->next;
            if(pSlow==pFast)
                break;
        }
        // if it is a circle
        if(pFast!=NULL){
            pSlow=pHead;
            while(pSlow!=pFast){
                pSlow=pSlow->next;;
                pFast=pFast->next;
            }
        }
         
        return pFast;
    }
};

参考文章:
1、判断两个单链表是否相交及找到第一个交点
2、链表中环的入口结点