連結清單相關算法

1.連結清單反轉

遞歸算法

ListNode* reverselist(ListNode *head)
{
    if(head==NULL or head->next==NULL)
        return head;
    ListNode *p=reverselist(head->next);
    head->next->next=head;
    head=NULL;
    return p;
}
           

非遞歸算法

ListNode* reverselist(ListNode *head)
{
    ListNode *cur=head;
    if(cur==NULL)
        return cur;
    ListNode *pre=NULL;
    while(cur!=NULL)
    {
        temp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=temp;
    }
    return pre;
}
           

2.單連結清單是否有環

bool hasCycle(ListNode *head)

{

    if(head==NULL or head->next==NULL)

        return false;

    ListNode *fast,*slow;

    slow=head;

    fast=head->next;

    while(fast&&fast->next)

    {

        slow=slow->next;

        fast=fast->next->next;

        if(slow==fast)

            return true;

    }

    return false;

}
           

3.單連結清單找環入口

ListNode* detectCycle(ListNode *head)

{

    if(head==NULL)

        return head;

    ListNode *fast,*slow;

    slow=head;

    fast=head;

    while(fast&&fast->next)

    {

        slow=slow->next;

        fast=fast->next->next;

        if(slow==fast)

        {

            ListNode *slow2=head;

            while(slow2!=slow)

            {

                slow=slow->next;

                slow2=slow2->next;

            }

            return slow2;

        }

    }

    return null;

}
           

4.單連結清單找交點

ListNode *getIntersectionNode(ListNode *headA,ListNode *headB)

{

    ListNode *pa=headA;

    ListNode *pb=headB;

    while(pa!=pb)

    {

        pa=pa!=NULL?pa->next:headB;

        pb=pb!=NULL?pb->next:headA;

    }

    return pa;

}
           

5.連結清單找中間點

ListNode* middleNode(ListNode *head)

{

    ListNode *slow=head;

    ListNode *fast=head;

    while(fast&&fast->next)

    {

        slow=slow->next;

        fast=fast->next->next;

    }

    return slow;

}
           

6.已排序連結清單合并

ListNode *mergeTwoLists(ListNode *l1,ListNode *l2)

{

    if(l1==NULL)

        return l2;

    if(l2==NULL)

        return l1;



    ListNode dummy(-1);

    ListNode *p=&dummy;

    for(;l1&&l2;p=p->next)

    {

        if(l1->val<l2->val)

        {

            p->next=l1;

            l1=l1->next;

        }

        else

        {

            p->next=l2;

            l2=l2->next;

        }

    }

    p->next=l1!=NULL?l1:l2;

    return dummy.next;

}