15道简单算法题

2014-6-9 15:37| 发布者: joejoe0332| 查看: 6098| 评论: 0|原作者: 陈太汉|来自: jobbole.com

摘要: 这15道大部分来自《剑指Offer》，作者的博客之前看过几次，感觉写得很好，但看这本书时却没有那个感觉了，可能是因为看过博客的原因吧，没有了之前的那种惊喜。自己就试着实现里面的一些算法题目，基本上是简单的思 ...

3:倒序打印一个单链表;

　　递归实现，先递归在打印就变成倒序打印了，如果先打印在调用自己就是顺序打印了。

//倒序打印一个单链表
void ReversePrintNode(NodeL* head)
{
    if (head)
    {
        ReversePrintNode(head->next);
        cout<<head->value<<endl;
    } 
} 
void ReversePrintNodeTest()
{
    NodeL* head=new NodeL();
    NodeL* cur=head;
    for (int i=1;i<10;i++)
    {
        NodeL* tmpNode=new NodeL(i);
        cur->next=tmpNode;
        cur=tmpNode;
    }
    ReversePrintNode(head);
}

4:给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点;

　　删除节点的核心还是将这个节点的下一个节点，代替当前节点。

//给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点
void DeleteNode(NodeL* head,NodeL* delNode)
{
    if (!head || !delNode)
    {
        return;
    }
 
    if (delNode->next!=NULL)//删除中间节点
    {
        NodeL* next=delNode->next;
        delNode->next=next->next;
        delNode->value=next->value;
        delete next;
        next=NULL;
    }else if (head==delNode)//删除头结点
    {
        delete delNode;
        delNode=NULL;
        *head=NULL;
    }else//删除尾节点，考虑到delNode不在head所在的链表上的情况
    {
        NodeL* tmpNode=head;
        while (tmpNode && tmpNode->next!=delNode)
        {
            tmpNode=tmpNode->next;
        }
        if (tmpNode!=NULL)
        {
            delete delNode;
            delNode=NULL;
            tmpNode->next=NULL;
        }
    }
}
 
void DeleteNodeTest()
{
    int nodeCount=10;
    for (int K=0;K<nodeCount;K++)
    {
        NodeL* head=NULL;
        NodeL* cur=NULL;
        NodeL* delNode=NULL;
        for (int i=0;i<nodeCount;i++)
        {
            NodeL* tmpNode=new NodeL(i);
            if (i==0)
            {
                cur=head=tmpNode;
            }else{
                cur->next=tmpNode;
                cur=tmpNode; 
            }
            if (i==K)
            {
                delNode=tmpNode;
            } 
        }
        DeleteNode(head,delNode) ;
    } 
}

5:找到链表倒数第K个节点;

　　通过两个指针，两个指针都指向链表的开始，一个指针先向前走K个节点，然后再以前向前走，当先走的那个节点到达末尾时，另一个节点就刚好与末尾节点相差K个节点。

//找到链表倒数第K个节点
NodeL* FindKthToTail(NodeL* head,unsigned int k)
{
    if(head==NULL || k==0)
        return NULL;
    NodeL* tmpNode=head;
    for (int i=0;i<k;i++)
    {
        if (tmpNode!=NULL)
        {
            tmpNode=tmpNode->next;
        }else{
            return NULL;
        } 
    }
    NodeL* kNode=head;
    while (tmpNode!=NULL)
    {
        kNode=kNode->next;
        tmpNode=tmpNode->next;
    }
    return kNode;
}
 
void FindKthToTailTest()
{
    int nodeCount=10;
    for (int K=0;K<nodeCount;K++)
    {
        NodeL* head=NULL;
        NodeL* cur=NULL; 
        for (int i=0;i<nodeCount;i++)
        {
            NodeL* tmpNode=new NodeL(i);
            if (i==0)
            {
                cur=head=tmpNode;
            }else{
                cur->next=tmpNode;
                cur=tmpNode;  
            }
        }
        NodeL* kNode=FindKthToTail(head,K+3) ;
        if (kNode)
        {
            cout<<"倒数第 "<<K+3<<" 个节点是："<<kNode->value<<endl;
        }else{
            cout<<"倒数第 "<<K+3<<" 个节点不在链表中" <<endl;
        }
    } 
}

6:反转单链表;

　　按顺序一个个的翻转就是了。

//反转单链表
NodeL* ReverseList(NodeL* head)
{
    if (head==NULL)
    {
        return NULL;
    }
    NodeL* reverseHead=NULL;
    NodeL* curNode=head;
    NodeL* preNode=NULL;
    while (curNode!=NULL)
    {
        NodeL* nextNode=curNode->next;
        if (nextNode==NULL)
            reverseHead=curNode;  
 
        curNode->next=preNode;
        preNode=curNode;
        curNode=nextNode;
    }
    return reverseHead;
}
 
void ReverseListTest()
{
    for (int K=0;K<=10;K++)
    {
        NodeL* head=NULL;
        NodeL* cur=NULL; 
        for (int i=0;i<K;i++)
        {
            NodeL* tmpNode=new NodeL(i);
            if (i==0)
            {
                cur=head=tmpNode;
            }else{
                cur->next=tmpNode;
                cur=tmpNode;  
            }
        }
 
        cur=ReverseList( head);
        while (cur)
        {
            cout<<cur->value<<" ";
            cur=cur->next;
        }
        cout<<endl;
    }
    cout<<endl;
}