我是一名有用的助手，可以为您进行翻译。
我正在学习一项考试，以下是一道来自旧考试的问题：
我们有一个带有列表头的单向链表，声明如下：
class Node {
Object data;
Node next;
Node(Object d,Node n) {
data = d;
next = n;
}
}
编写一个方法void addLast(Node header, Object x)，将x添加到列表末尾。
我知道如果我实际上有这样的东西：
LinkedList someList = new LinkedList();
我可以通过以下方式将项目添加到末尾：
list.addLast(x);
class Node {
Object data;
Node next;
Node(Object d,Node n) {
data = d ;
next = n ;
}
public static Node addLast(Node header, Object x) {
// save the reference to the header so we can return it.
Node ret = header;
// check base case, header is null.
if (header == null) {
return new Node(x, null);
}
// loop until we find the end of the list
while ((header.next != null)) {
header = header.next;
}
// set the new node to the Object x, next will be null.
header.next = new Node(x, null);
return ret;
}
}
您想使用循环遍历整个链表，并检查每个节点的“下一个”值。最后一个节点将是其下一个值为null的节点。只需将此节点的下一个值设置为您使用输入数据创建的新节点即可。
node temp = first; // starts with the first node.
while (temp.next != null)
{
temp = temp.next;
}
temp.next = new Node(header, x);
如果你跟踪尾节点，就不需要遍历列表中的每个元素。
只需更新尾节点指向新节点即可：
AddValueToListEnd(value) {
var node = new Node(value);
if(!this.head) { //if the list is empty, set head and tail to this first node
this.head = node;
this.tail = node;
} else {
this.tail.next = node; //point old tail to new node
}
this.tail = node; //now set the new node as the new tail
}
简单来说：
this.tail = node; 不会覆盖 this.tail.next 吗？ - arjayadspublic static Node insertNodeAtTail(Node head,Object data) {
Node node = new Node(data);
node.next = null;
if (head == null){
return node;
}
else{
Node temp = head;
while(temp.next != null){
temp = temp.next;
}
temp.next = node;
return head;
}
}
这是一个关于你链表类的部分解决方案，我把实现的其他部分留给了你，并且也把作为链表一部分的尾节点的好建议留给了你。
节点文件:
public class Node
{
private Object data;
private Node next;
public Node(Object d)
{
data = d ;
next = null;
}
public Object GetItem()
{
return data;
}
public Node GetNext()
{
return next;
}
public void SetNext(Node toAppend)
{
next = toAppend;
}
}
这里是一个链表文件：
public class LL
{
private Node head;
public LL()
{
head = null;
}
public void AddToEnd(String x)
{
Node current = head;
// as you mentioned, this is the base case
if(current == null) {
head = new Node(x);
head.SetNext(null);
}
// you should understand this part thoroughly :
// this is the code that traverses the list.
// the germane thing to see is that when the
// link to the next node is null, we are at the
// end of the list.
else {
while(current.GetNext() != null)
current = current.GetNext();
// add new node at the end
Node toAppend = new Node(x);
current.SetNext(toAppend);
}
}
}
addLast() 需要进行一些优化，因为 addLast() 内部的 while 循环具有 O(n) 的复杂度。以下是我的 LinkedList 实现。运行代码 ll.addLastx(i) 一次，然后再运行 ll.addLast(i)，您可以看到 addLastx() 和 addLast() 的处理时间有很大的差异。
Node.java
package in.datastructure.java.LinkedList;
/**
* Created by abhishek.panda on 07/07/17.
*/
public final class Node {
int data;
Node next;
Node (int data){
this.data = data;
}
public String toString(){
return this.data+"--"+ this.next;
}
}
LinkedList.java
package in.datastructure.java.LinkedList;
import java.util.ArrayList;
import java.util.Date;
public class LinkedList {
Node head;
Node lastx;
/**
* @description To append node at end looping all nodes from head
* @param data
*/
public void addLast(int data){
if(head == null){
head = new Node(data);
return;
}
Node last = head;
while(last.next != null) {
last = last.next;
}
last.next = new Node(data);
}
/**
* @description This keep track on last node and append to it
* @param data
*/
public void addLastx(int data){
if(head == null){
head = new Node(data);
lastx = head;
return;
}
if(lastx.next == null){
lastx.next = new Node(data);
lastx = lastx.next;
}
}
public String toString(){
ArrayList<Integer> arrayList = new ArrayList<Integer>(10);
Node current = head;
while(current.next != null) {
arrayList.add(current.data);
current = current.next;
}
if(current.next == null) {
arrayList.add(current.data);
}
return arrayList.toString();
}
public static void main(String[] args) {
LinkedList ll = new LinkedList();
/**
* @description Checking the code optimization of append code
*/
Date startTime = new Date();
for (int i = 0 ; i < 100000 ; i++){
ll.addLastx(i);
}
Date endTime = new Date();
System.out.println("To total processing time : " + (endTime.getTime()-startTime.getTime()));
System.out.println(ll.toString());
}
}
这里有一个提示，你有一个节点图形的链表，并且你始终保留对头部的引用，它是linkedList中的第一个节点。
next指向链表中的下一个节点，因此当next为null时，你已经到达了列表的末尾。
public class LinkedList {
Node head;
public static class Node{
int data;
Node next;
Node(int item){
data = item;
next = null;
}
}
public static void main(String args[]){
LinkedList ll = new LinkedList();
ll.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
ll.head.next = second;
second.next = third;
third.next = fourth;
fourth.next = null;
ll.printList();
System.out.println("Add element 100 to the last");
ll.addLast(100);
ll.printList();
}
public void printList(){
Node t = head;
while(n != null){
System.out.println(t.data);
t = t.next;
}
}
public void addLast(int item){
Node new_item = new Node(item);
if(head == null){
head = new_item;
return;
}
new_item.next = null;
Node last = head;
Node temp = null;
while(last != null){
if(last != null)
temp = last;
last = last.next;
}
temp.next = new_item;
return;
}
}
addLast(Node header, Object x)方法，用于在链表末尾添加元素。可搜索关键词 “Java 单向链表末尾添加元素” 以获取更多信息。 - Deepak