剑指 Offer 22. 链表中倒数第k个节点

题目

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解题方法一

 /**
     * 自己想的 实质是双指针
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：36.3 MB, 在所有 Java 提交中击败了27.58%的用户
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) return null;
        int len = 0;
        ListNode pre = head;
        while (pre != null){
            len++;
            pre = pre.next;
        }
        if (k > len) return null;
        if (k == len) return head;
        ListNode res = head;
        ListNode priority = head;
        while (k - 1 != 0){
            priority = priority.next;
            k--;
        }
        while (priority != null){
            priority = priority.next;
            if (priority == null){
                break;
            }
            res = res.next;
        }
        return res;
    }

解题方法二

/**
     * 顺序查找
     * 首先求出链表的长度 n，然后顺序遍历到链表的第 n−k 个节点返回即可。
     *
     * 时间复杂度：O(n)，其中 n 为链表的长度。需要两次遍历。
     * 空间复杂度：O(1)。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd2(ListNode head, int k) {
        int n = 0;
        ListNode node = null;
        // 求出链表的长度 n
        for (node = head; node != null; node = node.next) {
            n++;
        }
        // 序遍历到链表的第 n−k 个节点返回
        for (node = head; n > k; n--) {
            node = node.next;
        }
        return node;
    }

解题方法三

/**
     * 双指针
     *
     * 首先将fast 指向链表的头节点，然后向后走 k 步，则此时fast 指针刚好指向链表的第 k+1 个节点。
     * 将 slow 指向链表的头节点，同时 \slow 与 fast 同步向后走，当 fast 指针指向链表的尾部空节点时，
     * 则此时返回 slow 所指向的节点即可
     *
     *时间复杂度：O(n)，其中 n 为链表的长度。我们使用快慢指针，只需要一次遍历即可，复杂度为 O(n)。
     * 空间复杂度：O(1)。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd3(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

微信关注

WeChat