单链表的常用操作（二）

接上一篇单链表的基本操作，我又整理了一些链表常考的题目，并且不断更新中。。。
1.查找链表中倒数第k个节点以及删除倒数第k个节点

//给两个指针p和q，让其中一个指针p领先q指针k步，
//然后再同时移动p和q指针，当领先的指针p先到达链表尾部时，后面的指针q所指向的节点恰好为倒数第k个节点。
Node* GetKthNode(int k)
{
    Node *p=head;
    Node *q=head;

    while(k>1&&p->next!=NULL)
    {
        p=p->next;
        k--;
    }

    if(k>1||p==NULL)
        return NULL;

    while(p->next!=NULL)
    {
        q=q->next;
        p=p->next;
    }
    return q;
}
//删除倒数第k个节点
Node* DelKthNode(int k)
{
    Node *p=head;
    Node *q=head;

    while(k>1&&p->next!=NULL)
    {
        p=p->next;
        k--;
    }

    if(k>1||p==NULL)
        return NULL;

    Node *pre=q;//记录需要删除的前一个节点
    while(p->next!=NULL)
    {
        pre=q;
        q=q->next;
        p=p->next;
    }
    pre->next=q->next;

    return head;
}

2.求链表的中间节点

//给定两个指针p和q,让p指针走两步，同时q指针走一步。当p指针指向尾处或者尾处前一个结点时，中间值求得
//若链表长度为奇数，q所在节点即为中间节点；若链表长度为偶数，q所在节点即为中间两个节点的前一个（这里我们就让其返回前一个节点）。
int getMid()
{
    if(head==NULL||head->next==NULL)
        return 0;
    if(head->next->next==NULL)
        return head->data;

    Node *p=head;
    Node *q=head;

    while(p->next!=NULL&&p->next->next!=NULL)
    {
        p=p->next->next;
        q=q->next;
    }

    return q->data;
}

3.在o(1)的时间复杂度删除单链表中指定的某一节点

// 对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点  
//这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表，  
// 链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点  
 //然后删除下一个节点即可。要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1) 

void delNode(Node *head,Node *toDelete)
{
    if(head==NULL)
        return;

    if(head->next==NULL)
        head=NULL;
    else
    {
        if(toDelete->next!=NULL)//要删除的不是尾节点
        {
            toDelete->data=toDelete->next->data;
            toDelete->next=toDelete->next->next;
        }
        else
        {
            Node *node=head;
            while(node->next!=toDelete)
                node=node->next;
            node->next=NULL;
        }
    }

}

4.从尾到头打印单链表

//从尾到头打印节点
void reversePrintLink()
{
    if(head==NULL)
        return;

    stack<int>  s;
    Node* p=head;

    while(p!=NULL)
    {
        s.push(p->data);
        p=p->next;
    }

    int value=0;
    while(!s.empty())
    {
        value = s.top();//不能直接用pop()赋值,pop返回的是void类型
        s.pop();
        cout<<value<<" ";
    }
    cout<<endl;
}