首页 > > 程序设计 > C/C++ >

链表重点问题（下）

2018-06-17 21:25:24来源：未知阅读 ()

1.判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算每个算法的时间复杂度&空间复杂度

思路：还是通过快慢指针来解决，让fast指针每次走2个结点，慢指针一次走一个结点

时间复杂度为O(n) 空间复杂度O(1 )

注意：fast每次走3个 4个.. 结点是不行的。分析如下：

考虑清楚后，便可以写下代码：

//（1）判断链表是否带环
SListNode* SListIsCycle(SListNode* list) {
    assert(list);
    
    SListNode* fast = list;
    SListNode* slow = list;
    
    while(fast && fast->_next){  
        fast = fast->_next->_next;
        slow = slow->_next;
        
        if(slow == fast){
            return fast;   //返回相遇点地址 
        }
    }
    return NULL;
     
}


（2）求环长度   
思路如下：
把相遇点的下一个结点地址赋给cur ，cur按环遍历一圈，通过计算器count便可求得环长
时间复杂度O（n） 空间复杂度O（1）
int SListCycleLen(SListNode* meetNode){
    assert(meetNode);
    
    size_t count = 0;
    SListNode* cur = meetNode->_next;
    while(cur != meetNode){
        count++;
        cur = cur->_next;
    }
    
    return count+1;
}

（3）求入口点

如果说不太理解“slow和fast第一次相遇，slow没绕环走超过一圈”。可以考虑这样一种情况：

注：slow和fast同时从一个地方走，这种情况下它们之间相差距离是最大的（刚好一圈）。v(fast) = 2v(slow), fast先进入环内。

有了以上分析，不难写得如下代码：

//meet的下一个结点地址赋给cur，list，cur同时往后走，相遇点即是入口点
时间复杂度O（n） 空间复杂度O（1）

SListNode* SListEntryNode(SListNode* list, SListNode* meetNode) {
    assert(list && meetNode);
    
    SListNode* cur = meetNode;
    while(cur != list){
        cur = cur->_next;
        list = list->_next;
    }
    return cur;
}

2.判断两个链表是否相交，若相交，求交点。（假设链表不带环）

思路：
1.先遍历两链表求得长度分别为x1,x2;
2.让指向长链表的指针先走|x1 - x2|的长度
3.最后两指针同时走，直到相遇

SListNode* SListNonCircleIsCrossNode(SListNode* list1, SListNode* list2){
    assert(list1 && list2);
    
    size_t x1 = 0,x2 = 0;
    SListNode* cur1 = list1;  //注意定义中间变量来遍历，list1、list2是两链表的头指针，不能改变其指向，故不能用来遍历，
    SListNode* cur2 = list2;
    while(cur1){
        cur1 = cur1->_next;
        x1++;
    } 
    while(cur2){
        cur2 = cur2->_next;
        x2++;
    }
    
    SListNode* longList = list1;
    SListNode* shortList = list2;
    if(x2 > x1){
        longList = list2;
        shortList = list1;
    }
    int gap = abs(x1 - x2);  //abs() 调用求绝对值函数 
    while(gap--){
        longList = longList->_next;
    } 
    //两指针同时走
    while(longList){
        longList = longList->_next;
        shortList = shortList->_next;
        if(longList == shortList){
            return longList;     //返回交点地址 
        }
    } 
    return NULL;
}

3.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】

需分下面几种情况讨论：
   （1）都不带环，转换成2题。    
   （2）一个带环，一个不带环。那一定不相交（若相交了，原链表结构肯定被改变了）。      
   （3）都带环。都带环也分为以下三种情况（利用两个相遇点(M1,M2) 判断是否带环——让M1不动，M2走一圈，如果两个能相遇，那就相交，反之不相交）         
         ①不相交

从meet遍历一遍环，能找到meet2则判定两环是相交

        ②环外相交（入口点相同）——从入口点处把链表截断，问题就转换成求两个不带环链表相交点。

        ③环内相交（入口点不同）

SListNode* SListCrossNode(SListNode* list1, SListNode* list2){
    assert(list1 && list2);
    //情况①：都不带环，转到上题 
    if(!SListIsCycle(list1) && !SListIsCycle(list2)){
        SListNonCircleIsCrossNode(list1,list2);
    }
    
    //情况②：都带环 
    else if(SListIsCycle(list1) && SListIsCycle(list2)){
        SListNode* pMeetNode1 = SListIsCycle(list1);  //上题函数 
        SListNode* pMeetNode2 = SListIsCycle(list2);     
        SListNode* cur = pMeetNode1->_next;
        
        while(cur != pMeetNode1 || pMeetNode1 == pMeetNode2){
            if(cur == pMeetNode2){ //相交的情况
                SListNode* entry1 = SListEntryNode(list1, pMeetNode1); //返回list1入口点 
                SListNode* entry2 = SListEntryNode(list2, pMeetNode2); //返回list2入口点 
                
                if(entry1 == entry2){   //两入口点相同，环外相交 
                    entry1->_next = NULL;
                    return SListNonCircleIsCrossNode(list1 , list2);
                }
            
                
                else{                //两入口点不同，环内相交 
                    printf("有两个交点，分别就是两个入口点\n");
                    int n = 0;
                    scanf("%d",&n);
                    if(n) 
                    return entry1;
                    else
                    return entry2; 
                } 
            }
            cur = cur->_next;
        } 
        
    } 
    else return NULL;
    
}

4.求两个已排序单链表中相同的数据

思路：依次比较两指针所指内容，谁小往后移动，若指向相同，两指针同时往后移动

void UnionSet(SListNode* l1, SListNode* l2){
    assert(l1 && l2);
    
    while(l1 && l2){
        if(l1->_data < l2->_data){
            l1 = l1->_next;
        }
        else if(l1->_data > l2->_data){
            l2 = l2->_next;
        }
        else{
            printf("%d ",l1->_data);
            l1 = l1->_next;
            l2 = l2->_next;
        }
    } 
}

5.复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。

思路： ①复制原链表的每一个结点，把复制的结节点插在原节点的后面。
②依次对新结点的random处理，新结点的random所指结点就是原结点的random所指结点的下一个结点
③最后分离两个链表

typedef struct ComplexListNode 
{ 
    int _data; 
    struct ComplexListNode* _next; 
    struct ComplexListNode* _random; 
}CLNode; 

CLNode* BuyCLNode(int x)
{
    CLNode* newCLNode = (CLNode*)malloc(sizeof(CLNode));
    if (newCLNode != NULL)
    {
        newCLNode->_data = x;
        newCLNode->_next = NULL;
        newCLNode->_random = NULL;
    }
    return newCLNode;
}

CLNode* CopyComplexList(CLNode* list)   //复制复杂链表函数
{   
    assert(list);
    //拷贝链表
    CLNode* cur = list;
    while (cur != NULL)
    {
        CLNode* newCLNode = BuyCLNode(cur->_data);
        newCLNode->_next = cur->_next; 
        cur->_next = newCLNode;

        cur = newCLNode->_next;
    }

    //置random
    cur = list;
    while (cur)
    {
        CLNode* next = cur->_next;
        if (cur->_random )
        {
            next->_random = cur->_random->_next;
        }
        cur = next->_next;
    }


    //拆断两链表
    cur = list;
    CLNode* NewHead = cur->_next;  //NewHead作复制链表的头指针

    CLNode* next = cur->_next;
    CLNode* Nextnext = next->_next;

    while (cur != NULL)
    {
        cur->_next = Nextnext;
        if (next->_next != NULL)  //最后一次循环时，next->_next已指向NULL
        {
            next->_next = Nextnext->_next;
        }

        cur = Nextnext;
        if (cur != NULL)   //最后一次循环，Nextnext赋值给cur ，cur已指向NULL
        {
            next = cur->_next;
            Nextnext = next->_next;
        }
    }
    return NewHead;
}