剑指offer22:链表倒数第k个节点

题目：输入一个链表，输出该链表中倒数第k个结点.

链表长度未知，可以西安遍历一次得到链表长度，然后可计算出移动多少步. 然后这样做相当于遍历两次链表. 假如链表的倒数第K个节点存在，想要遍历一次就找到倒数第K个节点，设置两个指针指向头节点，让其中一个指针先走k-1步，然后两个指针一起向后移，当先走的指针走到链表尾时，另一个指针指向倒数第k个节点.

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==nullptr)
            return nullptr;
        if(k==0)
            return nullptr;
        ListNode* p1= pListHead;
        ListNode* p2= p1;
        for(int i=0;i<k-1;i++){
            if(p2->next!=nullptr){
                p2 = p2->next;
            }
            else{
                return nullptr;
            }
        }
        while(p2->next!=nullptr){
            p2 = p2->next;
            p1 = p1->next;
        }
        return p1;
    }

链表的中间节点：如果链表节点总数时奇数，返回中间节点，如果是偶数，返回中间两个的任意一个. 如果想要遍历一次，参考上诉思想，一个指针无法解决. 设置两个指针，两个指针同时出发，一个走一步，一个走两步，可以发现当走两步的指针走到表尾时，另一个指针刚好指向链表中间节点.

ListNode* FindMiddle(ListNode* pListHead){
    if(pListHead==nullptr)
        return nullptr;
    ListNode* p1=pListHead;
    ListNode* p2=p1;
    while(p2->next!=nullptr){
        p2 = p2->next;
        if(p2->next==nullptr)
            break;
        else:
            p1 = p1->next;
            p2 = p2->next;
    }
    return p1;
}

note:当对链表进行操作一个指针不能解决问题的时候，可以尝试用两个指针遍历链表，可以一快一慢，或让其中一个先走