5

情况

明天我有一个 TripAdvisor 的面试，我决定练习创建我自己的自定义 LinkedList。我试图找出穿越它的最佳方法。

主要问题：我已经设法遍历了我的链接列表，但是我相信有更好的方法来做到这一点。你将如何穿越它？

额外问题：我的整体课程看起来如何？有什么我应该/不应该添加的吗？它似乎工作正常，但它是最佳的吗？

额外问题#2：最后我想知道是否有人对我必须知道的典型面试问题/概念有任何见解？

非常感激。

这是我的课程

// *********************************Node Class*******************************************     
 public class Node<T> {
  Node<T> link;

  T data;

  public Node(T data) {

    this.data = data;
    link = null;

}

public T getData() {
    return data;

}

public Node<T> getLink() {

    return link;

}


public Node<T> setLink(Node<T> N) {

    this.link = N;
    return link;

}

public void setData(T newData) {

    this.data = newData;

}

}

    //****************************************Linked List Class*******************************

   public class LinkedList<T> {

Node<T> head;
T data;


public LinkedList(){
   head = null;
   }




public void add(T data){

    Node<T> newNode = new Node<T> (data);
    newNode.setLink(head);
    head = newNode;
}


  //had problems printing out the data in the last node

 public void traverse(){
    Node<T> pointer;
    pointer = head;

while (pointer.getLink()!=null){
        System.out.println(pointer.getData());
        pointer = pointer.setLink(pointer.getLink());
}

//Fixed problems For last node that doesnt get printed out
System.out.println(pointer.getData());

}

//同样有更好的方法来做到这一点吗？//谢谢 }

4

1 回答 1

5

我会将您的遍历功能更改为更像这样：

public void traverse(){
  Node<T> pointer = head;

  while (pointer != null){
    System.out.println(pointer.getData());
    pointer = pointer.getLink();
  }
}

此外，通常将 Node 类表示为 LinkedList 的私有内部类，因为它通常在其他任何地方都不需要。

就面试本身而言，遍历问题对于二叉树来说更为典型（例如，按排序顺序打印出元素）。LinkedList 问题更侧重于删除/插入操作，这两者都需要仔细注意边缘情况（例如，当您移除头部时会发生什么）。一个更高级的 LinkedList 问题会询问如何检测循环，我会确保我知道至少一种这样做的方法（看看Tortoise and the Hare algorithm）。

编辑：

算法问题几乎总是来自以下列表：

  • 字符串操作，例如：
    • 反向字符串
    • 计算每个字母在给定字符串中出现的次数（为此使用地图）
  • LinkedList 问题，例如：
    • 如何移除节点，密切关注移除头部等边缘情况
    • 如何反转linkedList（使Tail成为Head）
  • 二叉树问题，例如：
    • 中序遍历
    • 如果存在 BTree 平衡问题，您不需要实现它，只需了解完全不平衡的二叉树只是一个链表。
    • 了解与链接列表或完全不平衡的二叉树（O（n））相比，搜索平衡的二叉树是 O（log n）。
  • 您可能会被要求描述您刚刚给出的解决方案的复杂性（大 O 表示法）

有关与 Java 本身相关的问题，请参见this和this

于 2013-10-29T02:17:55.747 回答