随笔练——单链表相交问题

1.判断一个单链表是否有环


 

  • 借助STL里的 set ,java里用hashset是一样的,不需要排序,碰到重复key说明有环。
LNode *isloop(LinkList l) {
    LNode *p = l->next;
    set<LNode*>s;
    while (p) {
        if (s.find(p) != s.end()) {
            return p;
        }
        s.insert(p);
        p = p->next;
    }
    return NULL;
}
  • 不借助set也可以通过另一种方式:

一个正常指针一次走一个,一个快指针一次走两个。

如果链表有环,快指针一定会和慢指针相遇,相遇的时候,把快指针扔回头结点,然后两个指针都每次走一个,一定会在 环入口相遇。

LNode* isloop(LinkList l) {
    LNode *pp = l->next, *p = l->next;
    while (pp&&pp->next) {
        pp = pp->next->next;
        p = p->next;
        if (p == pp) {
            pp = l->next;
            while (p != pp) {
                pp = pp->next;
                p = p->next;
            }
            return p;
        }
    }
    return NULL;
}

完整测试代码:

随笔练——单链表相交问题
#include <iostream>
#include <set>
using namespace std;
typedef struct LNode {
    struct LNode *next;
    int data;
}*LinkList;

void push_back(LinkList l, int x) {
    LNode *p = l;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    while (p->next) {
        p = p->next;
    }
    s->next = p->next;
    p->next = s;
}

LinkList init() {
    LinkList l = (LinkList)malloc(sizeof(LNode));
    l->next = NULL;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        push_back(l, t);
    }
    return l;
}

void loop(LinkList l) {
    LNode *p = l->next;
    while (p->next)p = p->next;
    p->next = l->next->next->next;
}

LNode *isloop(LinkList l) {
    LNode *p = l->next;
    set<LNode*>s;
    while (p) {
        if (s.find(p) != s.end()) {
            return p;
        }
        s.insert(p);
        p = p->next;
    }
    return NULL;
}

LNode* isloop1(LinkList l) {
    LNode *pp = l->next, *p = l->next;
    while (pp&&pp->next) {
        pp = pp->next->next;
        p = p->next;
        if (p == pp) {
            pp = l->next;
            while (p != pp) {
                pp = pp->next;
                p = p->next;
            }
            return p;
        }
    }
    return NULL;
}
int main() {
    LinkList l = init();
    loop(l);
    cout << isloop1(l)->data << endl;
    return  0;
}
View Code

 

2.判断两个链表是否相交(无环)


 

  • 借助set,和第一题思想差不多。
  • 不借助set:

首先要搞清楚,如果两个链表相交的话,那他们的最后一个节点一定是同一个。(因为是单链表就一个next,不存在说相交了在分开)。

那么我们就要,先分别遍历两个链表,并得到两个链表的最后一个节点,判断如果是同一个,继续进行,让较长的链表先走掉多出来的长度(遍历时候获取长度),让两个链表在同一起跑线,然后一定会同时在 相交节点处 相遇。

LNode *isintersect(LinkList l1,LinkList l2) {
    LNode *p = l1->next, *q = l2->next;
    int lg1 = 1, lg2 = 1;
    while (p->next) {
        lg1++; 
        p = p->next;
    }
    while (q->next) {
        lg2++;
        q = q->next;
    }
    if (p != q) return NULL;
    int div = abs(lg1 - lg2);
    p = lg1 > lg2 ? l1->next : l2->next;
    q = lg1 > lg2 ? l2->next : l1->next;
    while (div--) {
        p = p->next;
    }
    while (q != p) {
        p = p->next;
        q = q->next;
    }
    return p;
}

 

3.判断两个有环链表是否相交


 要清楚,单链表相交了之后就分不开了,进了环就出不来了。

所以只有三种情况:1 不相交,2 相交一段时间后,共用一个环, 3 无相交点,直接入环

随笔练——单链表相交问题随笔练——单链表相交问题

 

没有进行测试,但思想正确,应该是不会写错的。

 

 

LNode* intersect(LinkList l1, LinkList l2) {
    LNode *p1 = isloop(l1);
    LNode *p2 = isloop(l2);
    if (p1 == p2 && p1 != NULL) {
        //说明是第二种
        LNode *t = p1->next;
        p1->next = NULL;
        LNode *q = isintersect(l1, l2);
        p1->next = t;
        return q;
    }
    LNode *t = p1;
    while (p1 != p2) {
        p1 = p1->next;
        if (p1 == t) {
            //第三种
            return p;
        }
    }
    //都没找到,无相交
    return NULL;
}

 

上一篇:链表的应用:两个有序链表序列的合并


下一篇:jquery仿邮箱文本输入框自动加载邮箱后缀