链表倒数第K个节点

问题

给定一个链表，返回链表中倒数第 K 个节点。

例如：链表 1 -> 2 -> 3 -> 4 -> 5，K = 2，返回节点 4。

解答

链表节点定义

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

双指针解法

function getKthFromEnd(head, k) {
  // 快慢指针都从头开始
  let fast = head;
  let slow = head;

  // 快指针先走 k 步
  for (let i = 0; i < k; i++) {
    if (fast === null) return null; // k 大于链表长度
    fast = fast.next;
  }

  // 快慢指针同时走，直到快指针到达末尾
  while (fast !== null) {
    fast = fast.next;
    slow = slow.next;
  }

  // 此时慢指针指向倒数第 k 个节点
  return slow;
}

测试代码

// 构建链表 1 -> 2 -> 3 -> 4 -> 5
function createList(arr) {
  let dummy = new ListNode(0);
  let curr = dummy;
  for (let val of arr) {
    curr.next = new ListNode(val);
    curr = curr.next;
  }
  return dummy.next;
}

let head = createList([1, 2, 3, 4, 5]);
let result = getKthFromEnd(head, 2);
console.log(result.val); // 4

递归解法

function getKthFromEnd(head, k) {
  let count = 0;
  let result = null;

  function traverse(node) {
    if (node === null) return;
    traverse(node.next);
    count++;
    if (count === k) {
      result = node;
    }
  }

  traverse(head);
  return result;
}

关键点

• 双指针法：快指针先走 k 步，然后快慢指针同时走，快指针到末尾时慢指针就是答案
• 快慢指针间距始终保持 k，当快指针为 null 时，慢指针距离末尾正好 k 个位置
• 边界处理：k 大于链表长度时返回 null
• 时间复杂度 O(n)，空间复杂度 O(1)
• 递归解法利用回溯计数，但空间复杂度为 O(n)