【剑指offer】19. 链表中倒数最后k个结点（java）

**剑指Offer19: 链表中倒数最后 k 个结点**

### 题目描述给定一个链表的头节点 head 和一个整数 k，返回链表中倒数第 k 个结点。

### 解决方案#### 方法一：使用栈实现我们可以使用栈来存储链表中的结点。然后，从栈顶开始取出 k 个结点，这些结点就是我们要找的倒数最后 k 个结点。

javapublic class Solution {
 public ListNode getKthNode(ListNode head, int k) {
 // 使用栈实现 Stack stack = new Stack<>();
 // 将链表中的结点压入栈中 while (head != null) {
 stack.push(head);
 head = head.next;
 }
 // 从栈顶开始取出 k 个结点 for (int i =0; i < k -1; i++) {
 stack.pop();
 }
 // 返回链表中倒数第 k 个结点 return stack.isEmpty() ? null : stack.pop();
 }
}

#### 方法二：使用双指针实现我们可以使用两个指针，一个从链表头开始向后移动，另一个从链表尾开始向前移动。两个指针之间的距离为 k 个结点。

javapublic class Solution {
 public ListNode getKthNode(ListNode head, int k) {
 // 使用双指针实现 ListNode p1 = head;
 ListNode p2 = head;
 // 将 p2 移动到链表尾部 while (p2.next != null) {
 p2 = p2.next;
 }
 // 将 p1 和 p2 之间的距离为 k 个结点 for (int i =0; i < k -1; i++) {
 p1 = p1.next;
 p2 = p2.prev;
 }
 // 返回链表中倒数第 k 个结点 return p1;
 }
}

#### 方法三：使用递归实现我们可以使用递归来找到链表中的倒数第 k 个结点。

javapublic class Solution {
 public ListNode getKthNode(ListNode head, int k) {
 // 使用递归实现 if (head == null || k <=0) {
 return null;
 }
 // 递归找到链表中的倒数第 k 个结点 ListNode node = getKthNode(head.next, k -1);
 // 如果 k 为1，则返回当前结点 if (k ==1) {
 return head;
 } else {
 // 否则，继续递归 return node;
 }
 }
}

### 总结以上是链表中倒数最后 k 个结点的三种解决方案。每种方法都有其优缺点和使用场景。选择哪种方法取决于具体问题的需求和限制。

###代码注释* 使用栈实现：该方法使用栈来存储链表中的结点，然后从栈顶开始取出 k 个结点。
* 使用双指针实现：该方法使用两个指针，一个从链表头开始向后移动，另一个从链表尾开始向前移动。两个指针之间的距离为 k 个结点。
* 使用递归实现：该方法使用递归来找到链表中的倒数第 k 个结点。

###代码示例以下是链表中倒数最后 k 个结点的代码示例：

javapublic class ListNode {
 int val;
 ListNode next;
 public ListNode(int val) {
 this.val = val;
 this.next = null;
 }
}

public class Solution {
 public ListNode getKthNode(ListNode head, int k) {
 // 使用栈实现 Stack stack = new Stack<>();
 while (head != null) {
 stack.push(head);
 head = head.next;
 }
 for (int i =0; i < k -1; i++) {
 stack.pop();
 }
 return stack.isEmpty() ? null : stack.pop();
 }
 public static void main(String[] args) {
 ListNode head = new ListNode(1);
 head.next = new ListNode(2);
 head.next.next = new ListNode(3);
 head.next.next.next = new ListNode(4);
 head.next.next.next.next = new ListNode(5);
 Solution solution = new Solution();
 ListNode kthNode = solution.getKthNode(head,3);
 System.out.println(kthNode.val); // 输出：3 }
}

以上是链表中倒数最后 k 个结点的代码示例。