链表中倒数第k个结点

问题陈述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

思路分析

普遍想法

首先获取链表的长度，然后将链表指到n-k位置即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
       if(head == null)    return null;   //判断链表是否为空

        //第一次遍历，得到链表长度
        ListNode first = head;
        int length = 0;

        while(first != null){
            length++;
            first = first.next;
        }

        //第二次遍历，得到倒数第k个元素
        int index = 0;
        ListNode second = head;

        while(second != null){
            if((length - k) == index){
                return second;
            }else{
                index++;
                second = second.next;
            }
        }

        return second;

    }
}

双指针解法

定义两个指针former和latter，初始都指向head。然后让former先走k个位置，这样两个指针间距为k，然后两指针同步前进，直到former为空，返回latter，即对应倒数第K个结点。

/**public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }**/
public class Get_from_Kth_to_end {
    public ListNode getKthToEnd(ListNode head , int k){
        ListNode former=head;
        ListNode latter=head;
        for(int i=0;i<k;i++){
            former=former.next;
        }
        while (former!=null){
            former=former.next;
            latter=latter.next;
        }
        return latter;

    }
    public static void main(String[] args){
        ListNode head=new ListNode(3);
        head.next=new ListNode(5);
        head.next.next=new ListNode(2);
        head.next.next.next=new ListNode(7);
        Get_from_Kth_to_end get_from_kth_to_end=new Get_from_Kth_to_end();
        System.out.println(get_from_kth_to_end.getKthToEnd(head,3).val);
    }
}