02.02 返回倒数第k个节点

难度

• 简单
• 中等

• [ ] 困难

  标签

  链表、双指针

  题目描述

  实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

  示例1：

  输入： 1->2->3->4->5 和 k = 2
  输出： 4

  给定的k保证是有效的

  题解

  1. 两次遍历

  /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int x) { val = x; }
  * }
  */
  class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode cur = head;
        int count = 1;
        while(cur.next != null) {
            cur = cur.next;
            count++;
        }
        int index = count - k + 1;
        ListNode result = head;
        while(--index > 0) {
            result = result.next;
        }
        return result.val;
    }
  }

2. 双指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode first = head;
        int x = k;
        while(--x > 0) {
            first = first.next;
        }
        ListNode result = head;
        while(first.next != null) {
            first = first.next;
            result = result.next;
        }
        return result.val;
    }
}