1.题目
输入一个链表,输出该链表中倒数第k个结点。
2.思路
Java代码,通过校验。代码思路如下:两个指针,先让第一个指针和第二个指针都指向头结点,然后再让第一个指正走(k-1)步,到达第k个节点。
然后两个指针同时往后移动,当第一个结点到达末尾的时候,第二个结点所在位置就是倒数第k个节点了。
3.程序
1 package first; 2 3 public class FindKthToTailTest { 4 public static void main(String[] args){ 5 ListNode head = new ListNode(); 6 ListNode second = new ListNode(); 7 ListNode third = new ListNode(); 8 ListNode forth = new ListNode(); 9 head.next = second;10 second.next = third;11 third.next = forth;12 head.val = 1;13 second.val = 2;14 third.val = 3;15 forth.val = 4;16 FindKthToTailTest test = new FindKthToTailTest();17 ListNode result = test.FindKthToTail(head, 1);18 System.out.println(result.val);19 }20 21 public ListNode FindKthToTail(ListNode head,int k){22 if(head == null || k <= 0){23 return null;24 }25 ListNode ANode = head;26 ListNode BNode = null;27 for(int i = 0;i