题目：输入一个链表，输出该链表中倒数第K个结点。为了符合大多数人的习惯，本体从1开始奇数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始他们的值一次是1、2、3、4、5、6.这个链表的倒数第3个结点是值为4的结点。
思路：先是一个指针往前走，走了k步之后，前后指针一起走，但是要注意特殊情景。
测试用例：
1）功能测试（第k个结点在链表的中间，第k个结点是链表的头结点，第k个结点是链表的尾结点）；
2）特殊输入测试（链表头结点为null指针，链表的结点总数少于k，k等于0）。
代码实现：
package com.yyq;/** * Created by Administrator on 2015/9/13. */public class FindKthToTail { public static ListNode findKthToTail(ListNode pListHead, int k){ if(pListHead == null || k <= 0) return null; ListNode pAead = pListHead; ListNode pBehind = null; for(int i = 0; i < k-1; i++){ if (pAead.getM_pNext() != null) pAead = pAead.getM_pNext(); else return null; } pBehind = pListHead; while(pAead.getM_pNext() != null){ pAead = pAead.getM_pNext(); pBehind = pBehind.getM_pNext(); } return pBehind; } public static void printList(ListNode pListHead){ if (pListHead == null) return; ListNode pNode = pListHead; while(pNode!= null){ System.out.print(pNode.getM_nValue()+" "); pNode = pNode.getM_pNext(); } System.out.println(); } // ====================测试代码==================== // 测试要找的结点在链表中间 public static void Test1() { System.out.println("=====Test1 starts:====="); ListNode pNode1 = new ListNode(1); ListNode pNode2 = new ListNode(2); ListNode pNode3 = new ListNode(3); ListNode pNode4 = new ListNode(4); ListNode pNode5 = new ListNode(5); ListNode pNode6 = new ListNode(6); pNode1.setM_pNext(pNode2); pNode2.setM_pNext(pNode3); pNode3.setM_pNext(pNode4); pNode4.setM_pNext(pNode5); pNode5.setM_pNext(pNode6); System.out.println("List: "); printList(pNode1); ListNode pNode = findKthToTail(pNode1, 2); if (pNode == null){ System.out.println("2th expected result is: " + pNode); }else{ System.out.println("2th expected result is: " + pNode.getM_nValue()); } System.out.println(); } // 测试要找的结点是链表的尾结点 public static void Test2() { System.out.println("=====Test2 starts:====="); ListNode pNode1 = new ListNode(1); ListNode pNode2 = new ListNode(2); ListNode pNode3 = new ListNode(3); ListNode pNode4 = new ListNode(4); ListNode pNode5 = new ListNode(5); ListNode pNode6 = new ListNode(6); pNode1.setM_pNext(pNode2); pNode2.setM_pNext(pNode3); pNode3.setM_pNext(pNode4); pNode4.setM_pNext(pNode5); pNode5.setM_pNext(pNode6); System.out.println("List: "); printList(pNode1); ListNode pNode = findKthToTail(pNode1, 1); if (pNode == null){ System.out.println("1th expected result is: " + pNode); }else{ System.out.println("1th expected result is: " + pNode.getM_nValue()); } System.out.println(); } // 测试要找的结点是链表的头结点 public static void Test3() { System.out.println("=====Test3 starts:====="); ListNode pNode1 = new ListNode(1); ListNode pNode2 = new ListNode(2); ListNode pNode3 = new ListNode(3); ListNode pNode4 = new ListNode(4); ListNode pNode5 = new ListNode(5); ListNode pNode6 = new ListNode(6); pNode1.setM_pNext(pNode2); pNode2.setM_pNext(pNode3); pNode3.setM_pNext(pNode4); pNode4.setM_pNext(pNode5); pNode5.setM_pNext(pNode6); System.out.println("List: "); printList(pNode1); ListNode pNode = findKthToTail(pNode1, 6); if (pNode == null) { System.out.println("6th expected result is: " + pNode); } else { System.out.println("6th expected result is: " + pNode.getM_nValue()); } System.out.println(); } // 测试空链表 public static void Test4() { System.out.println("=====Test4 starts:====="); ListNode pNode = findKthToTail(null, 100); if (pNode == null) { System.out.println("100th expected result is: " + pNode); } else { System.out.println("100th expected result is: " + pNode.getM_nValue()); } System.out.println(); } // 测试输入的第二个参数大于链表的结点总数 public static void Test5() { System.out.println("=====Test5 starts:====="); ListNode pNode1 = new ListNode(1); ListNode pNode2 = new ListNode(2); ListNode pNode3 = new ListNode(3); ListNode pNode4 = new ListNode(4); ListNode pNode5 = new ListNode(5); ListNode pNode6 = new ListNode(6); pNode1.setM_pNext(pNode2); pNode2.setM_pNext(pNode3); pNode3.setM_pNext(pNode4); pNode4.setM_pNext(pNode5); pNode5.setM_pNext(pNode6); System.out.println("List: "); printList(pNode1); ListNode pNode = findKthToTail(pNode1, 7); if (pNode == null) { System.out.println("7th expected result is: " + pNode); } else { System.out.println("7th expected result is: " + pNode.getM_nValue()); } System.out.println(); } // 测试输入的第二个参数为0 public static void Test6() { System.out.println("=====Test6 starts:====="); ListNode pNode1 = new ListNode(1); ListNode pNode2 = new ListNode(2); ListNode pNode3 = new ListNode(3); ListNode pNode4 = new ListNode(4); ListNode pNode5 = new ListNode(5); ListNode pNode6 = new ListNode(6); pNode1.setM_pNext(pNode2); pNode2.setM_pNext(pNode3); pNode3.setM_pNext(pNode4); pNode4.setM_pNext(pNode5); pNode5.setM_pNext(pNode6); System.out.println("List: "); printList(pNode1); ListNode pNode = findKthToTail(pNode1, 0); if (pNode == null) { System.out.println("0th expected result is: " + pNode); } else { System.out.println("0th expected result is: " + pNode.getM_nValue()); } System.out.println(); } public static void main(String[] args) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); }} 输出结果：
=====Test1 starts:=====
List:
1 2 3 4 5 6
2th expected result is: 5
=====Test2 starts:=====
List:
1 2 3 4 5 6
1th expected result is: 6
=====Test3 starts:=====
List:
1 2 3 4 5 6
6th expected result is: 1
=====Test4 starts:=====
100th expected result is: null
=====Test5 starts:=====
List:
1 2 3 4 5 6
7th expected result is: null
=====Test6 starts:=====
List:
1 2 3 4 5 6
0th expected result is: null