链表中倒数第k个结点

题目描述

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

解题思路一

将所有结点值存入容器，直接用索引值找到结果结点,时间复杂度O(n) ,空间复杂度O(n)

/**
     * 时间复杂度O(n) ,空间复杂度O(n)
     *
     * @param head
     * @param k
     * @return
     */
public ListNode FindKthToTail(ListNode head, int k) {
    if (head == null || k == 0)
        return null;
    //方法一，建立辅助空间arrayList存放所有结点
    List<ListNode> list = new ArrayList<ListNode>();
    while (head != null) {
        list.add(head);
        head = head.next;
    }
    if (Math.abs(k) > list.size())
        return null; //k值超出有效范围
    //对K进行处理，取余
    if (k < 0) {
        //倒数负数个也即是正序取第几个
        return list.get(Math.abs(k) - 1);
    } else {
        return list.get(list.size() - k);
    }

}

解题思路二

建立长度为K的滑窗，然后向右移动，直至滑窗右边界达到终点，那么滑窗左边界为所求,时间复杂度O(n)，空间复杂度O(1)

public ListNode FindKthToTail2(ListNode head, int k) {  //时间复杂度O(n)，空间复杂度O(1)
    if (head == null || k <= 0)
        return null;
    //创建滑窗，大小为K，不停向右移动，直到窗口右端到达边界，左端就是倒数K个
    ListNode left = head;
    ListNode right = head;
    //让right移动k-1个，创建滑窗
    while (k > 1){
        right = right.next;
        k --;
        if(right == null){
            //链表长度小于K，错误
            return null;
        }
    }
    //[left..right]同时向右移动
    while (right.next != null){
        left = left.next;
        right = right.next;
    }
    return left;
}