题目：输入一个链表，输出该链表中倒数第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