[剑指offer]链表中倒数第k个结点-白红宇

题目

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

/*public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/import java.util.ArrayList;import java.util.List;public class Solution {
         public ListNode FindKthToTail(ListNode head,int k) {    }}

解题思路

我的思路

遍历一遍链表，把每个数据存List，然后在从List中取出，当然存栈也是一种思想。

我的代码

/*public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/import java.util.ArrayList;import java.util.List;public class Solution {    public ListNode FindKthToTail(ListNode head,int k) {        if(head==null)            return null;         List
     
       list = new ArrayList
      
       ();         while(head!=null){             list.add(head);             head = head.next;         }        if(k>list.size()||k<=0)            return null;        return list.get(list.size()-k);    }}

看到他人代码，有更好的思路。

思路

两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指正走(k-1)步，到达第k个节点。然后两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了。

代码

/*public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode FindKthToTail(ListNode head,int k) {        if(head==null||k<=0){            return null;        }        ListNode pre=head;        ListNode last=head;               for(int i=1;i