题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路分析
- 采用双指针的方法，第一个指针首先向前移动k-1个位置，第二个指针指向头节点，然后将两个指针同时向后移动，如果第一个指针走到链表尾结点时，第二个指针的位置就正好为 倒数第k个节点
测试用例
- 功能测试：第k个节点在链表的中间;第k个节点是链表的头节点;第k个节点是链表的尾节点。
- 特殊输入测试：链表头节点为nullptr指针:链表的节点总数少于k;k等于0。
Java代码
public class Offer22 {
public static void main(String[] args) {
test1();
test2();
test3();
test4();
}
public static ListNode FindKthToTail(ListNode head, int k) {
return Solution1(head, k);
}
/**
* 双指针的方法
* @param head
* @param k
* @return
*/
private static ListNode Solution1(ListNode head, int k) {
if (head == null || k == 0) {
return null;
}
ListNode pBefore = head;
ListNode pBeHind = null;
for (int i = 0; i < k - 1; i++) {
if (pBefore.next != null) {
pBefore = pBefore.next;
} else {
return null;
}
}
pBeHind = head;
while (pBefore.next != null) {
pBefore = pBefore.next;
pBeHind = pBeHind.next;
}
return pBeHind;
}
private static void test1() {
ListNode head = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
head.next = node2;
node2.next = node3;
node3.next = node4;
ListNode kthNode = FindKthToTail(head, 4);
System.out.println("{1,2,3,4},4 ---> " + kthNode.val);
}
private static void test2() {
ListNode head = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
head.next = node2;
node2.next = node3;
node3.next = node4;
ListNode kthNode = FindKthToTail(head, 5);
if (kthNode == null) {
System.out.println("{1,2,3,4},5---> null ");
} else {
System.out.println("测试失败！");
}
}
private static void test3() {
ListNode head = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
head.next = node2;
node2.next = node3;
node3.next = node4;
ListNode kthNode = FindKthToTail(head, 0);
if (kthNode == null) {
System.out.println("{1,2,3,4},0---> null ");
} else {
System.out.println("测试失败！");
}
}
private static void test4() {
ListNode head = null;
ListNode kthNode = FindKthToTail(head, 4);
if (kthNode == null) {
System.out.println("{null},4---> null ");
} else {
System.out.println("测试失败！");
}
}
}