Java教程

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

本文主要是介绍力扣 - 剑指 Offer 22. 链表中倒数第k个节点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

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

思路1(栈)

  • 既然要倒数第k个节点,那我们直接把所有节点放到栈(先进后出)里面,然后pop弹出k个元素就可以了

代码

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        LinkedList<ListNode> stack = new LinkedList<>();

        // 把整个链表入栈
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        // 先将前n-1个元素出栈
        for (int i = 1; i < k; i++) {
            stack.pop();
        }

        // 此时位于栈顶的就是倒数第k个元素啦
        return stack.pop();
    }
}1

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(N)\),使用栈的额外空间要花掉\(O(N)\)

思路2(递归+回溯)

  • 使用栈的思想差不多。。
  • 先递归到链表末尾,然后依次回溯,回溯k次的时候就得到我们需要的节点了

代码

class Solution {
    ListNode res;
    // 代表当前处于倒数第几个节点
    int cur = 0;

    public ListNode getKthFromEnd(ListNode head, int k) {
        dfs(head, k);
        return res;
    }

    public void dfs(ListNode node, int k) {
        // 先递归到末尾
        if (node == null) {
            return;
        }

        dfs(node.next, k);

        // 倒数第cur个节点
        cur++;
        // 等于k代表找到了
        if (cur == k) {
            res = node;
        }
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(N)\),需要递归整个链表

思路3(双指针)

  • 定义fast快指针和slow慢指针两个指针:让快指针fast先走k步,然后再让两个指针同时移动,等快指针fast走道链表末尾时候(为null),此时慢指针slow所指向的节点就是倒数第k个节点

代码

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        // 让快指针先走k步,和慢指针相差k个距离
        for (int i = k; i > 0; i--) {
            fast = fast.next;
        }

        // 此时让慢指针和快指针同时走,知道快指针到达链表末尾为null时,慢指针就在倒数第k个位置上了
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 直接返回慢指针即为答案
        return slow;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(1)\)

思路4(差值法)

  • 因为要求的是倒数第k个节点,那如果我们知道了链表的总长度,那么这个节点在链表中的顺序位置也就知道了
  • 先计算出链表的总长度,则可以得出:倒数第k个节点 等于 链表总长度-k+1。但是在题目中我们已经指向了链表的第一个节点,所以只需要再走n-k个节点即可到达倒数第k个节点

代码

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int length = 0;
        ListNode p = head;

        // 先获取链表的总长度
        while (p != null) {
            p = p.next;
            length++;
        }

        // 其实倒数第k个的位置就相当于 length-k
        // 然后我们从链表头部开始遍历 length-k 个节点,此时所在的节点位置就是答案了
        k = length - k;
        for (int i = k; i > 0; i--) {
            head = head.next;
        }
        
        return head;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(1)\)
这篇关于力扣 - 剑指 Offer 22. 链表中倒数第k个节点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!