14链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

思路：
快慢指针

快指针先走k 步，然后快慢指针一起走
当快指针走到null 时，慢指针就是所求的倒数第ｋ个节点

ｔｉｐｓ：
判断ｋ是否越界是在快指针走的时候

 1 public class Solution {
 2     public ListNode FindKthToTail(ListNode head,int k) {
 3         // 边界条件
 4         if(head==null||head.next==null) return head;
 5         ListNode fast = head;
 6         ListNode slow = head;
 7         for(;k>0;k--){
 8             //如果k越界
 9             if(fast==null) return null;
10             fast=fast.next;
11         }
12         while(fast!=null){
13             fast=fast.next;
14             slow=slow.next;
15         }
16         return slow;
17     }
18 }

 1 public class Solution {
 2     public ListNode FindKthToTail(ListNode head,int k) {
 3         if(head == null || head.next==null) return head;
 4         ListNode fast = head;
 5         ListNode slow = head;
 6         for(int i = 0;i<k;i++){
 7             if(fast==null) return null;
 8             fast = fast.next;
 9             
10         }
11         while(fast!= null){
12             fast = fast.next;
13             slow =slow.next;
14         }
15         return slow;
16     }

20180307

 1 public class Solution {
 2     public ListNode FindKthToTail(ListNode head,int k) {
 3             if(head==null) return head;
 4             int cnt = 0;
 5             ListNode fast = head;
 6             ListNode slow = head;
 7             for(ListNode root = head;root != null;root = root.next)
 8                 cnt++;
 9             if(k>cnt||k<=0)return null;
10             for(int i = 0;i<k;i++)
11                 fast = fast.next;
12             while(k!=0 && fast!=null){
13                 fast = fast.next;
14                 slow = slow.next;
15             }
16             return slow;
17     }
18 }

C++:20180808

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindKthToTail(ListNode* head, unsigned int k) {
12         if(head==NULL) return NULL;
13         ListNode* fast = head;
14         ListNode* slow = head;
15         for(;k>0;k--){
16             if(fast==NULL)
17                 return NULL;
18             fast = fast->next;
19         }
20         while(fast!=NULL){
21             fast = fast->next;
22             slow = slow->next;
23             }
24         return slow;
25         }
26 };