遍历链表的最佳方法 - Java

Question

遍历链表的最佳方法 - Java

javalinked-listtraversal

5

情景介绍：

我明天要参加TripAdvisor的面试，为了练习，我决定创建自己的自定义LinkedList。我正试图找出最好的方法来遍历它。

主要问题：我已经成功地遍历了我的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());

}

//请问有更好的方法来完成这个任务吗？ //谢谢

- RonJermiah

你面试的职位是什么？ - PM 77-1

请尝试访问http://codereview.stackexchange.com/。 - Paul Samsotha

为什么你不能只使用 pointer = pointer.getLink(); 和 while (pointer != null) {（并删除你的最后一个Print语句）？ - Samuel O'Malley

涉及链表的面试问题通常会关注“删除”操作，因为它具有一些有趣的边缘情况。此外，一个常见的面试问题是：“如何检测循环链表或包含循环的链表？” - Samuel O'Malley

1

@omalsa04 谢谢您的见解！真不敢相信我自己没想到那个解决方案。 - RonJermiah

@PM77-1 一个Java开发实习岗位 - RonJermiah

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Samuel O'Malley · Accepted Answer

我会将您的遍历函数更改为以下方式：

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）。

编辑：

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

字符串操作，例如：
- 反转字符串
- 计算给定字符串中每个字母出现的次数（使用Map）
链表问题，例如：
- 如何删除节点，要特别注意删除头节点的情况
- 如何翻转链表（将尾节点变为头节点）
二叉树问题，例如：
- 中序遍历
- 如果有关于平衡二叉树的问题，你不需要实现它，只需理解完全不平衡的二叉树就是一个链表。
- 理解搜索平衡二叉树的复杂度是O(log n)，而搜索链表或完全不平衡的二叉树的复杂度是O(n)。
你可能会被要求描述你刚刚给出的解决方案的复杂度（大O符号）

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