面试题 02.02. 返回倒数第 k 个节点

方法一：使用外部空间

// 执行用时： 1 ms , 在所有 Java 提交中击败了 16.75% 的用户

// 内存消耗： 36.8 MB , 在所有 Java 提交中击败了 31.02% 的用户

class Solution {

    public int kthToLast(ListNode head, int k) {

		// 朴素的想法是用额外空间记录链表的值

        // 因为k都是有效的，所以不会出现越界的情况

        List<Integer> list = new ArrayList<>();

        while(head != null){

            list.add(head.val);

            head = head.next;

        }

        return list.get(list.size() - k);

    }

}

方法二：快慢指针

// 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户

// 内存消耗： 36.4 MB , 在所有 Java 提交中击败了 95.43% 的用户

class Solution {

    public int kthToLast(ListNode head, int k) {

		ListNode fast = head;

        while(k-- != 0){

            fast = fast.next;

        }

        while(fast != null){

            fast = fast.next;

            head = head.next;

        }

        return head.val;

    }

}

巴特西

面试题 02.02. [链表][双指针]返回倒数第 k 个节点

面试题 02.02. 返回倒数第 k 个节点

最新文章

热门文章