剑指offer 链表中倒数k个节点

目录

描述

方法一 双指针法

 方法二 栈

描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0≤n≤1050 leq n leq 10^50≤n≤105，0≤ai≤1090 leq a_i leq 10^90≤ai​≤109，0≤k≤1090 leq k leq 10^90≤k≤109

要求：空间复杂度 O(n)O(n)O(n)，时间复杂度 O(n)O(n)O(n)

进阶：空间复杂度 O(1)O(1)O(1)，时间复杂度 O(n)O(n)O(n)

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

方法一 双指针法

让另一个指针指向头结点，然后向后移k个节点，这样两个指针的查就是k，然后让两个指针每次都一起向后走一步，直到后面的指针到了null为止，这个时候前面的指针的位置就是我们想要的节点

java代码

 public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(pHead==null||k==0)return null;
        ListNode behind=pHead;
        while(behind!=null&&k>0){
            behind=behind.next;
            k--;
        }
        if(behind==null&&k>0) return null;
        while(behind!=null){
            pHead=pHead.next;
            behind=behind.next;
        }
        return pHead;
    }

 方法二 栈

创建一个栈，然后遍历链表，把每个节点都入栈，然后再出栈k-1个节点，这个时候的栈顶就是想要的节点了

java代码

public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead==null||k==0)return null;
        Stack stack=new Stack<>();
        while(pHead!=null){
            stack.push(pHead);
            pHead=pHead.next;
        }
        if(stack.size()1){
            stack.pop();
            k--;
        }
        return stack.peek();
    }