(转)常见的链表题目

一些常见的单链表题目，总结思路和实现代码。

1.单链表的反序

2.给单链表建环

3.检测单链表是否有环

4.给单链表解环

5.检测两条链表是否相交

6.不输入头节点，删除单链表的指定节点（只给定待删除节点指针）
7、将两个有序链表合并成一个有序链表——搜狐畅游笔试题归来  

1.单链表的反序（前插法）

2.给单链表建环

//给单链表建环，让尾指针，指向第num个节点，若没有，返回false
bool bulid_looplink(node *head, int num)
{
    node *cur = head;
    node *tail = NULL;
    int i = 0;
    if(num <= 0 || head == NULL)
    {
        return false;
    }
    for(i = 1; i < num; ++i)
    {
        if(cur == NULL)
        {
            return false;
        }
        cur = cur->next;
    }
    tail = cur;
    while(tail->next)
    {
        tail = tail->next;
    }
    tail->next = cur;
    return true;
}

3.检测单链表是否有环

4.给单链表解环

ps:为了增加节点位图的效率，本应使用hash或则红黑树，这里不造车了，直接用 set容器

5.检测两条链表是否相交

//检测两条链表是否相交，是则返回第一个交点，否则返回NULL
//思路：把2个链表各遍历一遍，记下长度length1和length2,若2者的尾节点指针相等，则相交。
//       之后再把长的链表从abs(len1-len2)的位置开始遍历，第一个相等的指针为目标节点
node* detect_intersect_links(node *first_link, node *second_link)
{
    int legnth1 = 1, length2 = 1, pos = 0;
    node *cur = NULL, *longer_link = first_link, *shorter_link = second_link;
    if(first_link == NULL || second_link == NULL)
    {
        return NULL;
    }
    while(first_link->next || second_link->next)     //遍历2个链表
    {
        if(first_link->next)
        {
            first_link = first_link->next;
            ++legnth1;
        }
        if(second_link->next)
        {
            second_link = second_link->next;
            ++length2;
        }
    }
    if(first_link != second_link)                 //比较尾节点
    {
        return NULL;
    }
    pos = legnth1 - length2;
    if(legnth1 < length2)                  //保证 longer_link为长链表
    {
        pos = length2 - legnth1;
        cur = longer_link;
        longer_link = shorter_link;
        shorter_link = cur;
    }
    while(pos-- > 0)
        longer_link = longer_link->next;
    while(longer_link || shorter_link)
    {
        if(longer_link == shorter_link)                  //找到第一个交点
        {
            return longer_link;
        }
        longer_link = longer_link->next;
        shorter_link = shorter_link->next;
    }
    return NULL;
}

6.不输入头节点，删除单链表的指定节点（只给定待删除节点指针）