求鏈表的中間結點

思路

一個走兩步，一個走一步。一個走到尾，另外一個就走到了中間

/*** 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;}
};