img

米智恬

Java/python/算法

xiaomi

个人博客

小米的个人博客，欢迎交流

每天一道剑指Offer：链表中倒数第k个结点

| 阅读：次

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

思路

⚠ 注意边界问题
⚠ 注意特判

  • 方法1：
    • 倒数第k个 = 第 (size-k) 个
      • —使用stack压入节点，再弹出k个
      • —直接使用链表数 size
  • 方法2：
    • –两个指针 p1，p2 都是从左到右移动，p1 先移动，指向 k-1 个数字
    • –然后 p2 与 p1 同时右移，直到 p1 移到最后一个 node 处
    • –此时 p2 指向的节点就是倒数第 k 个点

### 代码实现

方法一

import java.util.Stack;

ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k <= 0) return null;

        Stack<ListNode> nodeStack = new Stack<>();
        ListNode node = head;
        nodeStack.push(node);

        while (node.next != null) {
            node = node.next;
            nodeStack.push(node);
        }

        while (k > 1) {
            if (nodeStack.empty()) return null;
            nodeStack.pop();
            k--;
        }

        if (nodeStack.size() > 0)
            return nodeStack.pop();

        return null;
    }

方法二

 ListNode FindKthToTail(ListNode head, int k) {
         if (head == null || k <= 0) return null;

        ListNode p1 = new ListNode();
        ListNode p2 = new ListNode();
        p1 = head;
        p2 = head;
        while (k > 1) {
            if (p1.next == null) return null;
            p1 = p1.next;
            k--;
        }

        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
   }