跳到主要内容

TopK 题库

2024年04月09日
柏拉文
越努力，越幸运

一、查找倒数第 k 个节点​

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

1.1 双指针​

思路

快慢指针的思想。我们将第一个指针fast指向链表的第k + 1个节点，第二个指针slow指向链表的第一个节点，此时指针fast与slow二者之间刚好间隔k个节点。此时两个指针同步向后走，当第一个指针fast走到链表的尾部空节点时，则此时slow指针刚好指向链表的倒数第k个节点。

实现

function getKthFromEnd(head,k){
    let fast = head;
    let slow = head;
    while(fast && k>0){
        k = k-1;
        fast = fast.next;
    }
    while(fast){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

二、删除倒数第 k 个节点​

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例1

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

实例2

输入：head = [1], n = 1
输出：[]

2.1 栈​

思路

在遍历链表的同时将所有节点依次入栈。根据栈先进后出的原则，我们弹出栈的第n个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。

实现

function removeNthFromEnd(head,n){
  let dummy = new ListNode(0,head);
  let stack = [];
  let current = dummy;
  while(current != null){
    stack.push(current);
    current = current.next;
  }
  while(n>0){
    n = n-1;
    stack.pop();
  }
  let prev = stack.pop();
  prev.next = prev.next.next;
  let result = dummy.next;
  return result;
}

2.2 双指针​

思路

初始时first和second均指向头节点。我们首先使用first对链表进行遍历，遍历的次数为n。此时，first 和second之间间隔了n−1个节点，即first比second超前了n个节点。在这之后，我们同时使用first和second对链表进行遍历。当first遍历到链表的末尾（即first为空指针）时，second恰好指向倒数第n个节点。

如果我们能够得到的是倒数第n个节点的前驱节点而不是倒数第n个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将second指向哑节点，其余的操作步骤不变。这样一来，当first遍历到链表的末尾时，second的下一个节点就是我们需要删除的节点。

实现

function removeNthFromEnd(head,n){
  let dummy = new ListNode(0,head);
  let first = head;
  let second = dummy;
  while(first && n>0){
    n = n-1;
    first = first.next;
  }
  while(first){
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  let result = dummy.next;
  return result;
}