本章涵盖了您在编码面试中将遇到的最流行的编码挑战，涉及地图和链表。由于单链表在技术面试中是首选，本章中的大多数问题都将利用它们。但是，您也可以挑战自己并尝试在双向链表的上下文中解决每个此类问题。通常，对于双向链表，问题变得更容易解决，因为双向链表为每个节点维护两个指针，并允许我们在列表中来回导航。

到本章结束时，您将了解所有涉及链表和映射的常见问题，并且您将对许多技术有足够的知识和理解，以帮助您解决该类别中的任何其他问题。我们的议程很简单；我们将涵盖以下主题：

• 简而言之，链表
• 简而言之地图
• 编码挑战

本章中的所有代码文件都可以在 GitHub 上获得，并且可以在 https://github.com/PacktPublishing/The-Complete-Coding-Interview-Guide-in-Java/tree/master/Chapter11。

然而，在进入编码挑战之前，让我们先了解一下链表和映射。

链表是一个线性的 数据结构，表示节点序列。第一个节点通常被称为作为head，而最后一个节点是 通常称为 tail。当每个节点指向下一个节点时，我们有一个单链表，如下图所示：

图 11.1 – 单链表

当每个节点指向下一个节点和前一个节点时，我们就有了一个双向链表，如下图图表：

图 11.2 – 一个双向链表

让我们考虑一个单链表。如果尾部指向头部，那么我们就有一个循环单链表。或者，让我们考虑一个双向链表。如果尾部指向头部，头部指向尾部，那么我们有一个循环双向链表。

在单链表中，节点 保存数据（例如，整数或对象）和指向下一个节点的指针。以下代码表示单链表的节点：

private final class Node {
  private int data;
  private Node next;
}

双向链表还需要指向前一个节点的指针：

private final class Node {
  private int data;
  private Node next;
  private Node prev;
}

与数组不同，链表不提供恒定时间来访问 nth 元素。我们必须迭代 n-1 个元素以获得 nth 元素.我们可以从链表的开头（单次和双重）以恒定的时间插入、删除和更新节点。如果我们的实现管理双 链表的尾部（称为双头双向链表），那么我们可以在恒定时间内从链表的结尾为 好；否则，我们需要迭代链表直到最后一个节点。如果我们的实现管理单链表的尾部（称为双头单链表），那么我们可以在链表末尾以恒定时间插入节点;否则，我们需要迭代链表直到最后一个节点。

本书的代码包附带以下应用程序（每个应用程序都公开了 insertFirst()、insertLast()、insertAt()、delete()、deleteByIndex() 和 print() 方法）：

• SinglyLinkedList：双头单链表的实现
• SinglyLinkedListOneHead：单头单链表的实现
• DoublyLinkedList：双头双向链表的实现
• DoublyLinkedListOneHead：单头双向链表的实现

强烈建议您自己剖析这些应用程序中的每一个。它们中的每一个都经过大量评论，以帮助您理解每个步骤。以下编码挑战依赖于这些链表实现。

假设您正在字典中查找 单词。这个词本身是独一无二的，可以被认为是一个key。这个词的意思可以是考虑的值。因此，这个词和它的含义形成了一个键值对。类似地，在计算中，键值对容纳一段数据，通过键搜索可以找到其中的值。换句话说，我们知道键，我们可以用它来找到值。

地图是一种抽象数据类型 (ADT)，用于管理key-通过 数组的值对（称为条目）。地图的特征包括：

• 键是唯一的（即不允许重复键）。
• 我们可以查看键列表、值列表或两者。
• 使用地图最常用的方法是 get()、put() 和 删除（） 。

现在我们已经简要概述了链表和映射的 概念，让我们开始我们的编码挑战。

在接下来的 17 个编码挑战中，我们将涉及到一些涉及地图和链表的问题。由于链表是技术面试中比较热门的话题，我们会给他们分配更多的问题。但是，要掌握地图数据结构的概念，尤其是内置 Java 地图实现，我强烈建议您购买这本书 Java Coding Problems，该书也是 Packt Publishing 出版的（https://www.packtpub.com/programming/java-coding-problems）。除了作为本书的绝妙伴侣之外，Java 编码问题还包含以下地图问题（请注意，这不是完整的列表）：

• 创建不可修改/不可变的集合
• 映射默认值
• 计算 Map 中是否存在/不存在值
• 从 Map 中移除
• 替换 Map 中的条目
• 比较两张地图
• 对 Map 进行排序
• 复制 HashMap
• 合并两张地图
• 删除集合中与谓词匹配的所有元素

现在我们已经对链表和映射表有了基本的了解，让我们来看看面试中最常见的与映射表和链表有关的问题。

Coding challenge 1 – Map put, get, and remove

问题：编写地图数据结构的基本 实现，允许您放置、获取和删除值。您应该有一个名为 put(K k, V v) 的方法，一个名为 get(K k) 的方法，以及一个名为 remove(K k) 的方法。

解决方案：如您所知，地图是键值对数据结构。每个键值对都是映射的一个条目。因此，在实现条目之前，我们无法实现映射的功能。由于一个条目包含两条信息，因此我们需要定义一个以通用方法包装键和值的类。

代码很简单：

private final class MyEntry<K, V> {
  private final K key;
  private V value;
  public MyEntry(K key, V value) {
    this.key = key;
    this.value = value;
  }
  // getters and setters omitted for brevity
}

现在我们有了一个条目，我们可以声明一个映射。映射通过具有默认大小的条目数组进行管理，这称为 映射容量。初始容量为 16 个元素的映射声明如下：

private static final int DEFAULT_CAPACITY = 16;
private MyEntry<K, V>[] entries 
        = new MyEntry[DEFAULT_CAPACITY];

接下来，我们可以专注于使用这个数组来充当客户端的地图。只有当条目的键在整个地图中唯一时，才能将条目放入地图。如果给定的键存在，那么我们只需更新它的值。除此之外，只要我们没有超过 地图容量，我们就可以添加一个条目。在这种情况下，典型的方法是将地图的大小加倍。基于这些语句的代码如下：

private int size;
public void put(K key, V value) {
  boolean success = true;
  for (int i = 0; i < size; i++) {
    if (entries[i].getKey().equals(key)) {
      entries[i].setValue(value);
      success = false;
    }
  }
  if (success) {
    checkCapacity();
    entries[size++] = new MyEntry<>(key, value);
  }
}

下面的辅助方法用于将地图的容量加倍。由于 Java 数组无法调整大小，我们需要通过创建初始数组的副本来解决此问题，但 是初始数组大小的两倍：

private void checkCapacity() {
  if (size == entries.length) {
    int newSize = entries.length * 2;
    entries = Arrays.copyOf(entries, newSize);
  }
}

使用键来获取值。如果没有找到给定的键，那么我们返回 null。获取值不会从地图中删除条目。让我们看一下代码：

public V get(K key) {
  for (int i = 0; i < size; i++) {
    if (entries[i] != null) {
      if (entries[i].getKey().equals(key)) {
        return entries[i].getValue();
      }
    }
  }
  return null;
}

最后，我们需要使用密钥删除一个条目。从数组中删除一个元素涉及将剩余元素移动一个位置。元素移动后，倒数第二个和 最后一个元素相等。您可以通过取消数组的最后一个元素来避免内存泄漏。忘记这一步是一个常见的 错误：

public void remove(K key) {
  for (int i = 0; i < size; i++) {
    if (entries[i].getKey().equals(key)) {
      entries[i] = null;
      size--;
      condenseArray(i);
    }
  }
}
private void condenseArray(int start) {
  int i;
  for (i = start; i < size; i++) {
    entries[i] = entries[i + 1];
  }
  entries[i] = null; // don't forget this line
}

地图的生产实现比这里公开的要复杂得多（例如，地图使用桶）。但是，很可能，您不需要在面试中了解比此实现更多的。不过，最好向面试官提及这一点。 方式，您可以向他们展示您了解问题的复杂性并且您已经意识到了这一点。

完毕！完整的应用程序被命名为 Map。

Coding challenge 2 – Map the key set and values

问题：将之​​前的编码挑战视为地图数据结构的基本实现。使用返回一组键的方法（keySet()）和返回值集合的方法（values()）丰富这个实现 ）。

解决方案：返回一组键是一个简单的操作，涉及循环映射的键并将它们一个一个添加到 Set 。以下代码不言自明：

public Set<K> keySet() {
  Set<K> set = new HashSet<>();
  for (int i = 0; i < size; i++) {
    set.add(entries[i].getKey());
  }
  return set;
}

为了返回值的集合，我们循环映射并将值一个一个地添加到 List。我们使用 List 因为值可以包含重复项：

public Collection<V> values() {
  List<V> list = new ArrayList<>();
  for (int i = 0; i < size; i++) {
    list.add(entries[i].getValue());
  }
  return list;
}

完毕！这很简单；为生产实现的 映射远比此处显示的复杂。例如，值 被缓存而不是每次都被提取。向面试官提及这一点，以便她/他可以看到您了解生产地图的工作原理。花点时间检查 Java 内置的 Map 和 HashMap 源代码。

完整的应用程序被命名为 Map。

Coding challenge 3 – Nuts and bolts

Google、Adobe

问题：给定 n 个螺母和 n 个螺栓，考虑一对一-它们之间的一个映射。编写一段代码，以 的最小迭代次数在具体细节之间找到所有匹配项。

解决方案：让我们考虑一下具体细节由以下两个数组表示：

char[] nuts = {'$', '%', '&', 'x', '@'};
char[] bolts = {'%', '@', 'x', '$', '&'};

最直观的解决方案依赖于蛮力方法。我们可以选择一个螺母并迭代螺栓以找到它的配合。例如，如果我们选择 nuts[0]，我们可以找到它与 bolts[3] 的配对。此外，我们可以将 nuts[1] 与 bolts[0] 配对。该算法通过两个 for 语句实现非常简单，复杂度时间为 O(n2)。

或者，我们可以考虑对螺母和螺栓进行分类。这样，螺母和螺栓之间的匹配将自动对齐。这也可以，但不包括最小迭代次数。

为了获得最少的迭代次数，我们可以使用哈希映射。在这个哈希映射中，首先，我们将每个坚果作为键，并将其在给定的坚果数组中的位置作为值。接下来，我们迭代螺栓，并检查哈希映射是否包含每个螺栓作为键。如果哈希映射包含当前螺栓的键，那么我们找到了一个匹配项（一对）；否则，此螺栓不匹配。让我们看一下代码：

public static void match(char[] nuts, char[] bolts) {
  // in this map, each nut is a key and 
  // its position is as value
  Map<Character, Integer> map = new HashMap<>();
  for (int i = 0; i < nuts.length; i++) {
    map.put(nuts[i], i);
  }
  //for each bolt, search a nut
  for (int i = 0; i < bolts.length; i++) {
    char bolt = bolts[i];
    if (map.containsKey(bolt)) {
      nuts[i] = bolts[i];
    } else {
      System.out.println("Bolt " + bolt + " has no nut");
    }
  }
  System.out.println("Matches between nuts and bolts: ");
  System.out.println("Nuts: " + Arrays.toString(nuts));
  System.out.println("Bolts: " +Arrays.toString(bolts));
}

此代码的 运行时间 为 O(n)。完整的代码名为 NutsAndBolts。

Coding challenge 4 – Remove duplicates

亚马逊、谷歌、Adobe、微软

问题：考虑一个未排序的整数单链表。编写一段代码来删除重复项。

解决方案：一个简单的解决方案包括迭代给定的链表并将每个节点的数据存储在一个设置<整数>。但是，在将当前节点的数据添加到 Set 之前，我们会根据 Set 的当前内容检查数据。如果 Set 已经包含该数据，我们从链表中删除该节点；否则，我们只需将其数据添加到 Set。可以通过将前一个节点链接到当前节点的下一个节点来从单链表中删除一个节点。

下图说明了这种说法：

图 11.3 – 从单链表中删除一个节点

由于单链表只保存指向下一个节点的指针，因此我们无法知道当前节点之前的节点。诀窍是跟踪两个连续节点，从当前节点作为链表头开始，前一个节点作为 null。当前节点前进到下一个节点时，前一个节点前进到当前节点。让我们看一下将这些语句粘合在一起的代码：

// 'size' is the linked list size
public void removeDuplicates() {
  Set<Integer> dataSet = new HashSet<>();
  Node currentNode = head;
  Node prevNode = null;
  while (currentNode != null) {
    if (dataSet.contains(currentNode.data)) {
      prevNode.next = currentNode.next;
      if (currentNode == tail) {
        tail = prevNode;
      }
      size--;
    } else {
      dataSet.add(currentNode.data);
      prevNode = currentNode;
    }
    currentNode = currentNode.next;
  }
}

该方案工作在 O(n)的时间和空间复杂度，其中n是链表中的节点数.我们可以尝试另一种方法，将空间 复杂度降低到 O(1)。首先，让我们考虑下图作为后续步骤的指南：

图 11.4 – 从单链表中删除一个节点

这种方法使用两个 指针：

1. 当前节点，从链表的头部开始，逐个节点遍历链表，直到到达尾部（例如上图中，当前节点为第二个节点）。
2. runner节点，从与当前节点相同的地方开始，即链表的头部。

另外，runner节点遍历链表，检查每个节点的数据是否与当前节点的数据相等。当运行器代码遍历链表时，当前节点的位置保持固定。

如果运行器节点检测到重复项，则将其从链表中删除。当runner节点到达链表尾部时，当前节点前进到下一个节点，runner节点从当前节点开始再次遍历链表。因此，这是一个 O(n2) 时间复杂度算法，但具有 O(1) 空间复杂度。让我们看一下代码：

public void removeDuplicates() {
  Node currentNode = head;
  while (currentNode != null) {
    Node runnerNode = currentNode;
    while (runnerNode.next != null) {
      if (runnerNode.next.data == currentNode.data) {
        if (runnerNode.next == tail) {
          tail = runnerNode;
        }
        runnerNode.next = runnerNode.next.next;
        size--;
      } else {
        runnerNode = runnerNode.next;
      }
    }
    currentNode = currentNode.next;
  }
}

完整的代码是，名为LinkedListRemoveDuplicates。

Coding challenge 5 – Rearranging linked lists

Adobe、Flipkart、亚马逊

问题：考虑一个未排序的 单链整数列表和给定整数，n 。编写一段代码，重新排列 n 周围的节点。换句话说，到最后，链表将包含所有小于 n 的值，然后是所有大于 n。 节点的顺序可以更改，n 本身可以在大于 n。

解决方案：考虑给定的链表是 1 → 5 → 4 → 3 → 2 → 7 → null，n= 3.所以，3是我们的支点。其余节点应围绕此枢轴重新排列，以符合问题要求。该问题的一种解决方案是逐个节点迭代链表，并且将小于枢轴的每个节点放在头部，而将每个大于枢轴的节点放在尾部。下图帮助我们可视化这个解决方案：

图 11.5 – 链表重新排列

因此，值为 5、4 和 3 的节点被移动到尾部，而值为 2 的节点被移动到头部。到最后，所有小于 3 的值都在虚线的左侧，而 所有大于 3 的值都在虚线的右侧。我们可以把这个算法写成代码如下：

public void rearrange(int n) {
  Node currentNode = head;
  head = currentNode;
  tail = currentNode;
  while (currentNode != null) {
    Node nextNode = currentNode.next;
    if (currentNode.data < n) {
      // insert node at the head
      currentNode.next = head;
      head = currentNode;
    } else {
      // insert node at the tail
      tail.next = currentNode;
      tail = currentNode;
    }
    currentNode = nextNode;
  }
  tail.next = null;
}

完整的应用程序是名为LinkedListRearranging。

Coding challenge 6 – The nth to last node

Adobe、Flipkart、亚马逊、谷歌、微软

问题：考虑一个整数单链表和给定整数n。编写一段代码，将 nth 的值返回到最后一个节点。

Solution: We have a bunch of nodes and we have to find the nth node that satisfies a given constraint. Based on our experience from Chapter 8, Recursion and Dynamic Programming, we can intuit that this problem has a solution involving recursion. But we can also solve it via an iterative solution. Since the iterative solution is more interesting, I will present it here, while the recursive solution is available in the bundled code.

让我们用下图来展示算法（按照从上到下的图表）：

图 11.6 – 倒数第 n 个节点

因此，给定一个链表，2 → 1 → 5 → 9 → 8 → 3 → 7 → null，我们想要找到倒数第五个节点的值，即 5（你可以在顶部看到这个上图）。迭代 解决方案使用两个指针；让我们将它们表示为 runner1 和 runner2。最初，它们都指向链表的头部。在第 1 步（上图中间），我们将 runner1 从头部移动到 5th 到头（或 nth 到头）节点。这在从 0 到 5（或 n）的 for 循环中很容易实现。在第 2 步（上图底部），我们同时移动 runner1 和 runner2 直到 runner1 是 null。当 runner1 为 null 时，runner2 将指向倒数第五个到最后一个节点（或 nth 从头到尾）。在代码行中，我们按如下方式进行：

public int nthToLastIterative(int n) {
  // both runners are set to the start
  Node firstRunner = head;
  Node secondRunner = head;
  // runner1 goes in the nth position
  for (int i = 0; i < n; i++) {
    if (firstRunner == null) {
      throw new IllegalArgumentException(
             "The given n index is out of bounds");
    }
    firstRunner = firstRunner.next;
  }
  // runner2 run as long as runner1 is not null
  // basically, when runner1 cannot run further (is null), 
  // runner2 will be placed on the nth to last node
  while (firstRunner != null) {
    firstRunner = firstRunner.next;
    secondRunner = secondRunner.next;
  }
  return secondRunner.data;
}

完整的应用程序是命名为LinkedListNthToLastNode。

Coding challenge 7 – Loop start detection

Adobe、Flipkart、亚马逊、谷歌、微软

问题：考虑一个包含循环的整数的单链表。换句话说，链表的尾部指向定义循环或循环的先前节点之一。编写一段代码，检测循环的第一个节点（即循环开始的节点）。

解决方案：如果我们管理链表的尾节点，那么很明显搜索到的节点（循环开始）在尾。下一个。如果我们不管理尾部，那么我们可以搜索有两个节点指向它的节点。这也很容易实现。如果我们知道链接的列表的size，那么我们可以从0迭代到size，最后一个node.next 指向标记循环开始的节点。

The Fast Runner/Slow Runner approach

但是，让我们尝试另一种需要更多想象力的 算法。这种方法称为 Fast Runner/Slow Runner 方法。这很重要，因为它可以用于涉及链表的某些问题。

首先，Fast Runner/Slow Runner 方法涉及使用两个指针，它们从链表的头部开始并同时遍历链表，直到满足特定条件。一个指针被命名为 Slow Runner (SR)，因为它逐个节点地遍历列表。另一个指针被命名为 Fast Runner (FR)，因为它通过在每次移动时跳过下一个节点来遍历列表。下图是四个动作的示例：

图 11.7 – 快跑者/慢跑者示例

所以，第一步，FR 和 SR 指向 head。第二步，SR指向值为1的head.next节点，而 FR 指向值为 4 的 head.next.next 节点。移动继续遵循此模式。当FR到达链表尾部时，SR指向中间节点。

正如您将在下一个编码挑战中看到的那样，Fast Runner/Slow Runner 方法可用于检测链表是否为回文。但是，现在，让我们继续我们的问题。那么，我们是否可以用这种方法来检测链表是否有循环，并找到这个循环的起始节点呢？这个问题产生了另一个问题。如果我们将 Fast Runner/Slow Runner 方法应用于具有循环的链表，FR 和 SR 指针是否会发生冲突或遇见？答案是肯定的，它们会碰撞。

为了解释这一点，我们假设在开始循环之前，我们有 q 个前面的节点（这些节点是 在环形）。对于 SR 遍历的每个 q 个节点，FR 已经遍历了 2*< em class="italic">q 个节点（这很明显，因为 FR 在每次移动时都会跳过一个节点）。因此，当SR 进入循环（到达循环开始节点）时，FR已经遍历了2*q 个节点。换句话说，FR 在循环部分的 2*q-q 个节点处；因此，它位于循环部分的 q 个节点处。让我们通过以下测试用例来可视化这一点：

图 11.8 – 带有循环的链表

因此，当 SR 进入循环（到达第四个节点）时，FR 到达第四个节点进入循环。当然，我们需要考虑q（前面的非循环节点数）可能远大于循环长度；因此，我们应该将 2*q-q 表示为 Q=modulo(q, LOOP_SIZE)。

例如，考虑 Q = modulo(3, 8) =3，其中我们有三个非循环节点 (q= 3) 循环大小为 8 (LOOP_SIZE=8)。在这种情况下，我们也可以应用 2*q-q，因为 2*3-3=3。因此，我们可以得出结论，SR 位于列表开头的三个节点处，FR 位于列表开头的三个节点处的循环。但是，如果链表在 7 个节点的循环之前有 25 个节点，则 Q = modulo (25, 7) = 4 个节点，而 2*25-25=25 ，这是错误的。

除此之外，FR 和 SR 在循环内移动。由于它们是在一个圆圈中移动，这意味着 当 FR 远离 SR< /em>，它也更接近 SR，反之亦然。下图隔离了循环并显示了它如何继续移动 FR 和 SR 直到它们发生碰撞：

图 11.9 – FR 和 SR 冲突

花点时间跟踪 SR 和 FR 直到他们到达集合点。我们知道 FR 位于 LOOP_SIZE – Q 节点后面 FR 并且SR 是 FR 后面的 Q 个节点。在我们的测试用例中，FR 在 SR 后面有 8-3=5 个节点，而 SR 比 FR 落后 3 个节点。通过继续移动SR和FR，我们可以看到FR以每步 1 步的速度上升。

那么，他们在哪里见面呢？好吧，如果 FR 以每步 1 步的速度赶上，并且 FR 是 LOOP_SIZE - SR 后面的 Q 个节点，那么它们将在循环头部之前遇到 Q 个步骤。在我们的测试用例中，它们将在值为 8 的节点处循环头部之前遇到 3 个步骤。

如果汇合点在循环头部的Q个节点，我们可以继续回忆汇合点在q 个节点也来自循环的头部，因为 Q=modulo(q, LOOP_SIZE)。这意味着我们可以开发以下四步算法：

1. 从链表头部的 FR 和 SR 开始。
2. 以 1 个节点的速率移动 SR，以 2 个节点的速率移动 FR。
3. 当它们发生碰撞时（在交汇点），将 SR 移动到链表的头部，并将 FR 保持在原处。
4. 以 1 个节点的速度移动 SR 和 FR 直到它们发生碰撞（这是表示 循环）。

让我们把它放到代码中：

public void findLoopStartNode() {
  Node slowRunner = head;
  Node fastRunner = head;
  // fastRunner meets slowRunner
  while (fastRunner != null && fastRunner.next != null) {
    slowRunner = slowRunner.next;
    fastRunner = fastRunner.next.next;
    if (slowRunner == fastRunner) { // they met
      System.out.println("\nThe meet point is at 
        the node with value: " + slowRunner);
      break;
    }
  }
  // if no meeting point was found then there is no loop
  if (fastRunner == null || fastRunner.next == null) {
    return;
  }
  // the slowRunner moves to the head of the linked list
  // the fastRunner remains at the meeting point
  // they move simultaneously node-by-node and 
  // they should meet at the loop start
  slowRunner = head;
  while (slowRunner != fastRunner) {
    slowRunner = slowRunner.next;
    fastRunner = fastRunner.next;
  }
  // both pointers points to the start of the loop
  System.out.println("\nLoop start detected at 
      the node with value: " + fastRunner);
}

作为一个简短的说明，不要期望 FR 可以跳过 SR，所以他们不会见面。这种情况是不可能的。假设 FR 跳过了 SR 并且它在节点 a 处，那么 SR 必须在节点 a-1。这意味着，在上一步中，FR 位于节点 a-2 和 SR 在节点 (a-1)-1=a-2;因此，它们发生了碰撞。

完整的应用程序被命名为LinkedListLoopDetection。在这段代码中，您会发现一个名为 generateLoop() 的方法。调用此方法以生成带有循环的随机链表。

Coding challenge 8 – Palindromes

Adobe、Flipkart、亚马逊、谷歌、微软

问题：考虑一个 单链整数列表。如果链表是回文，则编写一个返回 true 的 代码片段。解决方案应该涉及 Fast Runner/Slow Runner 方法（这种方法在之前的编码挑战中有详细说明）。

解决方案：作为一个快速提醒，回文（无论是字符串、数字还是链表）在反转时看起来没有变化。这意味着可以从两个方向处理（读取）回文，并且将获得相同的结果（例如，数字 12321 是回文，而数字 12322 不是）。

我们可以通过思考当 FR 到达链表末尾时，SR 在链表的中间。

如果链表的前半部分是后半部分的逆，则链表是回文。因此，如果在堆栈中，我们将 SR 遍历的所有节点存储起来，直到 FR 到达链表的末尾， 结果堆栈将以相反的顺序包含链表的前半部分。让我们通过下图可视化这一点：

图 11.10 – 使用 Fast Runner/Slow Runner 方法的链表回文

所以，当 FR 已经到达链表的 末端并且SR已经到了第四个节点（链表的中间），栈中包含了2、1、4的值。接下来，我们可以继续以一定的速度移动SR 1 个节点，直到链表的末尾。在每次移动时，我们从堆栈中弹出一个值，并将其与当前节点值进行比较。如果我们发现一个 不匹配，那么这个链表就不是一个 回文。在代码中，我们有以下内容：

public boolean isPalindrome() {
  Node fastRunner = head;
  Node slowRunner = head;
  Stack<Integer> firstHalf = new Stack<>();
  // the first half of the linked list is added into the stack
  while (fastRunner != null && fastRunner.next != null) {
    firstHalf.push(slowRunner.data);
    slowRunner = slowRunner.next;
    fastRunner = fastRunner.next.next;
  }
  // for odd number of elements we to skip the middle node
  if (fastRunner != null) {
    slowRunner = slowRunner.next;
  }
  // pop from the stack and compare with the node by node of 
  // the second half of the linked list
  while (slowRunner != null) {
    int top = firstHalf.pop();
    // a mismatch means that the list is not a palindrome
    if (top != slowRunner.data) {
      return false;
    }
    slowRunner = slowRunner.next;
  }
  return true;
}

完整的应用程序是命名为LinkedListPalindrome。

Coding challenge 9 – Sum two linked lists

Adobe、Flipkart、微软

问题：考虑两个正 整数和两个单链表。第一个整数逐位存储在第一个链表中（第一个数字是第一个链表的头部）。第二个整数逐位存储在第二个链表中（第一个数字是第二个链表的头部）。编写一段代码，将这两个数字相加，并将总和作为每个节点一个数字的链表返回。

解决方案：让我们从一个测试用例的可视化开始：

图 11.11 – 将两个数字相加为链表

如果我们逐步计算上图的总和，我们会得到以下结果：

我们加上 7 + 7 = 14，所以我们写下 4 并进位 1：

结果链表是 4 → ?

我们加上 3 + 9 + 1 = 13，所以我们写下 3 并进位 1：

结果链表是 4 → 3 → ?

我们加 8 + 8 + 1 = 17，所以我们写下 7 并进位 1：

结果链表是 4 → 3 → 7 → ?

我们加 9 + 4 + 1 = 14，所以我们写下 4 并进位 1

结果链表是 4 → 3 → 7 → 4 → ?

我们加上 4 + 1 = 5，所以我们写下 5 并且什么都不带：

结果链表是 4 → 3 → 7 → 4 → 5 → ?

我们加 1 + 0 = 1，所以我们写下 1 并且什么都不带：

结果链表是 4 → 3 → 7 → 4 → 5 → 1 → ?

我们加 2 + 0 = 2，所以我们写下 2 并且什么都不带：

结果链表为 4 → 3 → 7 → 4 → 5 → 1 → 2

如果我们把结果链表写成一个数字，我们得到4374512；因此，我们需要将其反转为 2154734。虽然可以在捆绑代码中找到用于反转结果链表的 方法（这本身可以被视为编码挑战），但以下方法以递归方法应用前面的步骤（如果您不擅长递归问题，请不要忘记涵盖 第 8 章，递归和动态规划）。本质上，以下递归通过逐个节点添加数据来工作，将任何多余的数据传递到下一个节点：

private Node sum(Node node1, Node node2, int carry) {
  if (node1 == null && node2 == null && carry == 0) {
    return null;
  }
  Node resultNode = new Node();
  int value = carry;
  if (node1 != null) {
    value += node1.data;
  }
  if (node2 != null) {
    value += node2.data;
  }
  resultNode.data = value % 10;
  if (node1 != null || node2 != null) {
    Node more = sum(node1 == null
        ? null : node1.next, node2 == null
        ? null : node2.next, value >= 10 ? 1 : 0);
    resultNode.next = more;
  }
  return resultNode;
}

完整的应用程序被命名为 LinkedListSum。

Coding challenge 10 – Linked lists intersection

Adobe、Flipkart、Google、微软

问题：考虑两个单链表。编写一段代码，检查两个列表是否相交。交集是基于参考，而不是值，但是你应该返回交集节点的值。因此，通过引用检查交集并返回值。

解决方案：如果您不确定两个链表的交集是什么意思，那么我们建议您绘制一个测试用例并与面试官讨论细节。下图显示了这种情况：

图 11.12 – 两个列表的交集

在这个图中，我们有两个在值为 8 的节点处相交的列表。因为我们谈论的是引用交集，这意味着值为 9 和值为 4 的节点指向值为 8 的节点。

主要问题是列表的大小不同。如果它们的大小相等，我们可以逐个节点地从头到尾遍历它们，直到它们发生碰撞（直到 node_list_1.next= node_list_2.next）。如果我们可以跳过值为 2 和 1 的节点，我们的列表将具有相同的大小（参见下图；由于第一个列表比第二个列表长，我们应该从标记为 虚拟头):

图片 11.13 – 删除顶部列表的前两个节点

牢记这句话，我们可以推导出以下算法：

1. 确定列表的大小。
2. 如果第一个列表（我们将其表示为 l1）比第二个列表（我们将其表示为 l2）长，那么将第一个列表的指针移动到 (l1-l2)。
3. 如果第一个列表比第二个短，则将第二个列表的指针移动到 (l2-l1)。
4. 逐个节点移动两个 指针，直到到达终点或它们发生碰撞。

将这些步骤 放入代码很简单：

public int intersection() {
  // this is the head of first list
  Node currentNode1 = {head_of_first_list};
  // this is the head of the second list
  Node currentNode2 = {head_of_second_list};
  // compute the size of both linked lists
  // linkedListSize() is just a helper method
  int s1 = linkedListSize(currentNode1);
  int s2 = linkedListSize(currentNode2);
  // the first linked list is longer than the second one
  if (s1 > s2) {
    for (int i = 0; i < (s1 - s2); i++) {
      currentNode1 = currentNode1.next;
    }
  } else {
    // the second linked list is longer than the first one
    for (int i = 0; i < (s2 - s1); i++) {
      currentNode2 = currentNode2.next;
    }
  }
  // iterate both lists until the end or the intersection node
  while (currentNode1 != null && currentNode2 != null) {
    // we compare references not values!
    if (currentNode1 == currentNode2) {
      return currentNode1.data;
    }
    currentNode1 = currentNode1.next;
    currentNode2 = currentNode2.next;
  }
  return -1;
}

完整的应用程序被命名为 LinkedListsIntersection。在代码中，您将看到一个名为 generateTwoLinkedListWithInterection() 的辅助方法。这用于生成具有交点的 随机列表。

Coding challenge 11 – Swap adjacent nodes

亚马逊、谷歌

问题：考虑一个单独的 链表。编写一段代码，交换相邻节点，使 1 → 2 → 3 → 4 → null 等列表变为 2 → 1 → 4 → 3 → null。考虑交换 相邻节点，而不是它们的值！

Solution：我们可以减少寻找交换两个连续节点n1和n2。交换两个值（例如，两个整数，v1 和 v2）的著名技术依赖于辅助变量和可以写成如下：

aux = v1; v1 = v2； v2 = 辅助；

但是，我们不能将这种简单的方法应用于节点，因为我们必须处理它们的链接。编写以下内容是不够的：

aux = n1; n1 = n2; n2 = 辅助；

如果我们依靠这种简单的方法将 n1 与 n2 交换，那么我们将获得类似于下图的内容（注意将 n1 与 n2 交换后，我们有 n1.next = n3 和 n2.next = n1，这是完全错误的）：

图 11.14 – 带有断开链接的普通交换 (1)

但是我们可以修复链接，对吗？好吧，我们可以显式设置 n1.next 指向 n2，并设置 n2。 next 指向 n3：

n1.next = n2

n2.next = n3

现在应该好了！我们可以交换两个连续的节点。但是，当我们交换一对节点时，我们也会 断开两对连续节点之间的链接。下图说明了这个问题（我们交换并修复了 n1-n2 对和 n3-n4 对的链接） ：

图 11.15 – 带有断开链接的普通交换 (2)

请注意，在 交换这两对之后，n2.next 指向 n4 ，这是错误的。因此，我们也必须修复此链接。为此，我们可以存储n2，在交换n3-n4后，我们可以通过设置n2.next=n3。现在，一切看起来都不错，我们可以将其放入代码中：

public void swap() {
  if (head == null || head.next == null) {
    return;
  }
  Node currentNode = head;
  Node prevPair = null;
  // consider two nodes at a time and swap their links
  while (currentNode != null && currentNode.next != null) {
    Node node1 = currentNode;           // first node
    Node node2 = currentNode.next;      // second node                    
    Node node3 = currentNode.next.next; // third node            
    // swap node1 node2
    Node auxNode = node1;
    node1 = node2;
    node2 = auxNode;
    // repair the links broken by swapping
    node1.next = node2;
    node2.next = node3;
    // if we are at the first swap we set the head
    if (prevPair == null) {
      head = node1;
    } else {
      // we link the previous pair to this pair
      prevPair.next = node1;
    }
    // there are no more nodes, therefore set the tail
    if (currentNode.next == null) {
      tail = currentNode;
    }
    // prepare the prevNode of the current pair
    prevPair = node2;
    // advance to the next pair
    currentNode = node3;
  }
}

完整的应用程序被命名为LinkedListPairwiseSwap。考虑挑战自己交换n个节点的序列。

Coding challenge 12 – Merge two sorted linked lists

亚马逊、谷歌、Adobe、微软， Flipkart

问题：考虑两个排序的单链表。编写一个 代码片段，将这两个列表合并，无需额外空间。

解决方案：所以，我们有两个排序列表，list1：4 → 7 → 8 → 10 → null 和 list2: 5 → 9 → 11 → null，我们要得到结果，4 → 5 → 7 → 8 → 9 → 10 → 11 → null。此外，我们希望在不分配新节点的情况下获得此结果。

由于我们无法分配新节点，因此我们必须从这些列表中选择一个成为最终结果或合并链表。也就是说，我们可以从list1作为合并链表开始，从list2中添加节点到 list1。处理完每个比较后，我们将指针 ( list1) 移动到合并列表中的最后一个节点。

例如，我们首先比较这两个列表的头部。如果list1的头部小于list2的头部，我们选择的头部list1 作为合并列表的头部。否则，如果 list1 的头部大于 list2 的头部，我们交换头部。下图说明了此步骤：

图 11.16 – 合并两个排序的链表（步骤 1）

由于 list1 的头部小于 list2 的头部（4 < 5），因此成为合并后的头部列表。我们说过 list1 会指向合并列表的最后一个节点；因此， 比较的下一个节点应该是 list1.next（值为 7 的节点）和 list2（值为 5 的节点）。下图显示了这种比较的结果：

图 11.17 – 合并两个排序的链表（步骤 2）

因为 list1 遵循合并后的列表（最终结果），所以我们必须将 list1.next 移动到值为 5 的节点，但我们 不能直接这样做。如果我们说 list1.next=list2，那么我们会丢失 list1 的其余部分。因此，我们必须执行交换，如下所示：

Node auxNode = list1.next; // auxNode = node with value 7
list1.next = list2;        // list1.next = node with value 5
list2 = auxNode;           // list2 = node with value 7

接下来，我们将list1移动到list1.next，也就是值为9的节点。我们比较list.next 与 list2;因此，我们将 9 与 7 进行比较。下图显示了此比较的结果：

图 11.18 – 合并两个排序的链表（步骤 3）

因为 list1 跟随合并后的列表（最终结果），所以我们必须将 list1.next 移动到值为 7 的节点（因为 7 < 9)，我们使用前面讨论过的交换来做到这一点。接下来，我们将list1移动到list1.next，也就是值为8的节点。我们比较list.next 与 list2;因此，我们将 8 与 9 进行比较。下图显示了此比较的结果：

图 11.19 – 合并两个排序的链表（步骤 4）

由于 8 < 9、不需要交换。我们将 list1.next 移动到下一个节点（值为 10 的节点）并将 10 与 9 进行比较。下图显示了此比较的结果：

图 11.20 – 合并两个已排序的链表（步骤 5）

由于 list1 遵循 合并列表（最终结果），我们必须移动 list1。接下来 到值为 9 的节点（因为 9 < 10），我们使用前面讨论的交换来完成。接下来，我们将list1移动到list1.next，也就是值为11的节点。我们比较list.next 与 list2;因此，我们将 11 与 10 进行比较。下图显示了此比较的结果：

图 11.21 – 合并两个排序的链表（步骤 6）

因为 list1 遵循 合并列表（最终结果），所以我们必须移动 list1。接下来 到值为 10 的节点（因为 10 < 11），我们使用前面讨论过的交换来完成。接下来，我们将list1移动到list1.next，即null；因此，我们从 list2 中复制剩余部分。下图显示了此比较的 结果：

图 11.22 – 合并两个排序的链表（最后一步）

至此，合并链表就完成了。是时候揭示代码了（这个方法被添加到众所周知的SinglyLinkedList中）：

public void merge(SinglyLinkedList sll) {
  // these are the two lists
  Node list1 = head;      // the merged linked list 
  Node list2 = sll.head;  // from this list we add nodes at 
                          // appropriate place in list1
  // compare heads and swap them if it is necessary
  if (list1.data < list2.data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
  // compare the nodes from list1 with the nodes from list2
  while (list1.next != null) {
    if (list1.next.data > list2.data) {
      Node auxNode = list1.next;
      list1.next = list2;
      list2 = auxNode;
    }
    // advance to the last node in the merged linked list              
    list1 = list1.next;
  }
  // add the remaining list2
  if (list1.next == null) {
    list1.next = list2;
  }
}

完整的 应用程序被命名为LinkedListMergeTwoSorted。类似的问题可能需要您通过递归合并两个排序的链表。虽然您可以找到这个名为LinkedListMergeTwoSortedRecursion的应用程序，我建议您挑战自己来尝试实现。此外，基于这种递归实现，挑战自己合并 n 链表。完整的应用程序 被命名为LinkedListMergeNSortedRecursion。

Coding challenge 13 – Remove the redundant path

问题：考虑一个在矩阵中存储路径的单个 链表。节点的数据类型是 (row, column)，或者简而言之，是 (r, c)。路径只能是水平的（按列）或垂直的（按行）。完整的路径由所有水平和垂直路径的端点给出；因此，中间点（或中间点）是多余的。编写一段代码，删除多余的路径。

解决方案：让我们考虑一个包含以下路径的链表：(0, 0) → (0, 1) → (0, 2) → (1, 2) → (2 , 2) → (3, 2) → (3, 3) → (3, 4) → 空值。冗余路径包括以下节点：(0, 1)、(1, 2)、(2, 2) 和 (3, 3)。因此，在删除冗余路径之后，我们应该保留一个包含四个节点的列表：(0, 0) → (0, 2) → (3, 2) → (3, 4) → null。下图表示冗余路径：

图 11.23 – 冗余路径

去掉冗余路径后，我们得到下图：

图 11.24 – 去除冗余后的剩余路径

前面的图表应该为这个问题提供了一个解决方案。请注意，定义垂直路径的节点具有相同的列，因为我们仅在行上向下/向上移动，而定义水平路径的节点具有相同的行，因为我们仅在列上向左/向右移动。这意味着如果我们考虑三个连续节点对于列或行具有相同的值，那么我们可以删除中间节点。对相邻三元组重复此 过程将删除所有冗余节点。代码 应该很容易理解：

public void removeRedundantPath() {
  Node currentNode = head;
  while (currentNode.next != null 
          && currentNode.next.next != null) {
    Node middleNode = currentNode.next.next;
    // check for a vertical triplet (triplet with same column)
    if (currentNode.c == currentNode.next.c
            && currentNode.c == middleNode.c) {
      // delete the middle node
      currentNode.next = middleNode;
    } // check for a horizontal triplet 
    else if (currentNode.r == currentNode.next.r
            && currentNode.r == middleNode.r) {
      // delete the middle node
      currentNode.next = middleNode;
    } else {
      currentNode = currentNode.next;
    }
  }
}

完整的应用程序是命名为LinkedListRemoveRedundantPath。

Coding challenge 14 – Move the last node to the front

问题：考虑一个 单链表。编写一段代码，通过两种方法将 最后一个节点移到前面。因此，链表的最后一个节点成为它的头。

解决方案：这种问题听上去很简单，其实很简单。第一种方法将遵循以下步骤：

1. 将指针移动到倒数第二个节点（我们将其表示为 currentNode）。
2. 存储 currentNode.next（我们将其表示为 nextNode - 这是最后一个节点）。
3. 将 currentNode.next 设置为 null （因此，最后一个节点变为尾巴）。
4. 将新的 head 设置为存储节点（因此，head 变为 nextNode）。

在代码行中，我们有以下内容：

public void moveLastToFront() {      
  Node currentNode = head;
  // step 1
  while (currentNode.next.next != null) {
    currentNode = currentNode.next;
  }
  // step 2
  Node nextNode = currentNode.next;
  // step 3
  currentNode.next = null;
  // step 4
  nextNode.next = head;
  head = nextNode;
}

第二种 方法可以通过以下步骤执行：

1. 将指针移动到倒数第二个节点（我们将其表示为 currentNode）。
2. 将链表 转换为循环链表（将 currentNode.next.next 链接到头部）。
3. 将新头设置为 currentNode.next。
4. 通过将 currentNode.next 设置为 null 来打破循环。

在代码行中，我们有以下内容：

public void moveLastToFront() {
  Node currentNode = head;
  // step 1
  while (currentNode.next.next != null) {
    currentNode = currentNode.next;
  }
  // step 2
  currentNode.next.next = head;
  // step 3
  head = currentNode.next;
  // step 4
 currentNode.next = null;
}

完整的应用程序是，名为LinkedListMoveLastToFront。

Coding challenge 15 – Reverse a singly linked list in groups of k

亚马逊、谷歌、Adobe、微软

问题：考虑一个 单链表和一个整数k。编写一段代码，在 k 组中反转链表的节点。

解决方案：让我们考虑给定的链表是 7 → 4 → 3 → 1 → 8 → 2 → 9 → 0 → null 并且 k=3。结果应该是 3 → 4 → 7 → 2 → 8 → 1 → 0 → 9 → null。

让我们考虑给定的 k 等于链表的大小。在这种情况下，我们将问题简化为反转给定的链表。例如，如果给定的列表是 7 → 4 → 3 → null 并且 k=3，那么结果应该是 3 → 4 → 7 → null。那么，我们怎样才能得到这个结果呢？

为了反转节点，我们需要当前节点（current），当前节点旁边的节点（next） ，以及当前节点之前的节点（previous），我们应用以下算法来表示节点的重新排列：

1. 从 0 开始的计数器。
2. As the current node (initially the head) is not null and we haven't reached the given k, the following occurs:

   一个。 next 节点（最初是 null）成为 current 旁边的节点节点（最初是头部）。

   湾。 current 节点旁边的节点（最初是 head）成为 previous 节点（最初是 空）。

   C。 previous 节点成为 current 节点（最初是头部）。

   d。 当前节点成为下一个节点（来自step 2a的节点） .

   e.增加计数器。

所以，如果我们应用这个算法，我们 可以反转整个列表。但是我们需要在组中扭转它；因此，我们必须解决我们所做工作的 k 个子问题。如果这听起来像是对 你的递归，那么你是对的。上述算法结束时，step 2a处设置的节点（next）指向计数器所指向的节点也是。我们可以说我们已经反转了第一个 k 个节点。接下来，我们通过从 next 节点开始的递归继续处理下一组 k 节点。下图说明了这个想法：

图 11.25 – 反转 k 组中的列表 (k=3)

下面的代码实现了这个想法：

public void reverseInKGroups(int k) {
  if (head != null) {
    head = reverseInKGroups(head, k);
  }
}
private Node reverseInKGroups(Node head, int k) {
  Node current = head;
  Node next = null;
  Node prev = null;
  int counter = 0;
  // reverse first 'k' nodes of linked list
  while (current != null && counter < k) {
    next = current.next;                        
    current.next = prev;            
    prev = current;
    current = next;
    counter++;
  }
  // 'next' points to (k+1)th node            
  if (next != null) {
    head.next = reverseInKGroups(next, k);
  }
  // 'prev' is now the head of the input list 
  return prev;
}

此代码 运行时间为 O(n)，其中 n 是< /a> 给定的列表。完整的应用程序被命名为 ReverseLinkedListInGroups。

Coding challenge 16 – Reverse a doubly linked list

微软, Flipkart

问题：考虑一个双向链表。编写一段反转其节点的代码片段。

解决方案：反转双向链表可以利用双向链表维护到前一个节点的链接这一事实。这意味着我们可以简单地交换每个节点的前一个指针和下一个指针，如下面的代码所示：

public void reverse() {
  Node currentNode = head;
  Node prevNode = null;
  while (currentNode != null) {
    // swap next and prev pointers of the current node
    Node prev = currentNode.prev;
    currentNode.prev = currentNode.next;
    currentNode.next = prev;
    // update the previous node before moving to the next node
    prevNode = currentNode;
    // move to the next node in the doubly linked list            
    currentNode = currentNode.prev;
  }
  // update the head to point to the last node
  if (prevNode != null) {
    head = prevNode;
  }
}

完整的应用程序被命名为DoublyLinkedListReverse。要对单链表和双链表进行排序，请参考第14章 ，排序和搜索。

Coding challenge 17 – LRU cache

亚马逊、谷歌、Adobe、微软， Flipkart

问题：编写一段代码来实现固定大小的LRU缓存。 LRU 缓存代表最近最少使用的缓存。这个的意思是，当缓存已满时，添加一个新条目会指示缓存自动驱逐最近最少使用的条目.

解决方案：任何缓存实现都必须提供快速有效的数据检索方式。这意味着我们的实现必须遵守以下约束：

• 固定大小：缓存必须使用有限的内存量。因此，它需要有一些界限（例如，固定大小）。
• 快速访问数据：插入和搜索操作应该很快；最好是 O(1) 复杂度时间。
• 快速驱逐数据：当缓存已满时（已达到分配的界限），缓存应该授权一种高效的算法来驱逐条目。

在最后一个要点的上下文中，从LRU缓存中逐出意味着逐出最近最少使用的数据。为此，我们必须跟踪最近使用的条目以及长时间未使用的条目。此外，我们必须确保插入和搜索操作的复杂性时间为 O(1)。 Java 中没有内置的数据结构可以为我们提供开箱即用的缓存。

但是我们可以从 HashMap 数据结构开始。在 Java 中，HashMap 允许我们在 O(1) 时间内通过键插入和搜索（查找）数据。因此，使用 HashMap 解决了一半的问题。另一半，即跟踪最近使用的条目和长时间未使用的条目，无法通过 HashMap 完成。

但是，如果我们想象一个提供快速插入、更新和删除的数据结构，那么我们必须考虑一个双向链表。本质上，如果我们知道双向链表中节点的地址，那么插入、更新和删除都可以在 O(1) 内完成。

这意味着我们可以提供一个依赖于 HashMap 和双向链表之间共生关系的实现。本质上，对于 LRU 缓存中的每个条目（键值对），我们可以将条目的键和关联的链表节点的地址存储在 HashMap 中，而该节点将存储条目的值。下图是该语句的直观表示：

图 11.26 – 使用 HashMap 和双向链表的 LRU 缓存

但是双向链表如何帮助我们跟踪最近使用的条目呢？秘密依赖于 以下几点：

• 在缓存中插入一个新的 条目将导致将相应的节点添加到链表的头部（因此，链表的头部保存了最近使用的值）。
• 当一个条目被访问时，我们将其对应的节点移动到链表的头部。
• 当我们需要驱逐一个条目时，我们驱逐链表的尾部（因此，链表的尾部保存了最近最少使用的值）。

那么，基于这些陈述，我们可以提供以下简单的实现：

public final class LRUCache {
  private final class Node {
    private int key;
    private int value;
    private Node next;
    private Node prev;
  }
  private final Map<Integer, Node> hashmap;
  private Node head;
  private Node tail;
  // 5 is the maximum size of the cache
  private static final int LRU_SIZE = 5;
  public LRUCache() {
    hashmap = new HashMap<>();
  }
  public int getEntry(int key) {
    Node node = hashmap.get(key);
    // if the key already exist then update its usage in cache
    if (node != null) {
      removeNode(node);
      addNode(node);
      return node.value;
    }
    // by convention, data not found is marked as -1
    return -1;
  }
  public void putEntry(int key, int value) {
    Node node = hashmap.get(key);
    // if the key already exist then update 
    // the value and move it to top of the cache                 
    if (node != null) { 
      node.value = value;
      removeNode(node);
      addNode(node);
    } else {
      // this is new key
      Node newNode = new Node();
      newNode.prev = null;
      newNode.next = null;
      newNode.value = value;
      newNode.key = key;
      // if we reached the maximum size of the cache then 
      // we have to remove the  Least Recently Used
      if (hashmap.size() >= LRU_SIZE) { 
        hashmap.remove(tail.key);
        removeNode(tail);
        addNode(newNode);
      } else {
        addNode(newNode);
      }
      hashmap.put(key, newNode);
    }
  }
  // helper method to add a node to the top of the cache
  private void addNode(Node node) {
    node.next = head;
    node.prev = null;
    if (head != null) {
      head.prev = node;
    }
    head = node;
    if (tail == null) {
      tail = head;
    }
  }
  // helper method to remove a node from the cache
  private void removeNode(Node node) {
    if (node.prev != null) {
      node.prev.next = node.next;
    } else {
      head = node.next;
    }
    if (node.next != null) {
      node.next.prev = node.prev;
    } else {
      tail = node.prev;
    }
  }   
}

完整的应用程序被命名为LRUCache。

嗯，这是本章的最后一个编码挑战。是时候总结本章了！

本章将您的注意力带到了涉及链表和映射的最常见问题上。在这些问题中，涉及单链表的问题是首选；因此，本章主要关注这类编码挑战。

在下一章中，我们将解决与堆栈和队列相关的编码挑战。