链表题目--2 求链表的中间结点 和 求链表中倒数第k个结点

求链表的中间结点

思路

一个走两步，一个走一步。一个走到尾，另外一个就走到了中间

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast=head;
    struct ListNode* slow=head;

    while(1)
    {
        if(head==NULL)
        {
            return NULL;
        }
        fast=fast->next;
        if(fast==NULL){
            break;
        }

        slow=slow->next;
        fast=fast->next;
        if(fast == NULL)
        {
            break;
        }
    }
    return slow;
}

求链表中倒数第k个结点

思路

让一个人先走k步，然后一起走，等最后一个为空时，前面那个就是倒数第k个结点

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
         ListNode *front = pListHead;
         ListNode *back = pListHead; 
        
        for(int i = 0; i < k; i++ ){
            if(front == NULL){
                return NULL;
            }
            front = front->next; 
        }
        
        while(front != NULL){
            front = front->next;
            back = back->next;
        }
        return back;
    }
};