不允许使用 Java 链表 API。
列表节点内可以有链表吗？如果是，如何将数据插入到列表节点中的链表中？
List Node 类（我尝试将一个新的链表添加到列表节点中，我猜这有效吗？）：
public class ListNode {
public Object data;
public ListNode next;
public LinkedList testLL;
// for normal only head/tails
public ListNode(Object data) {
this.data = data;
this.next = null;
this.testLL = null;
}
// for normal nodes in the middle
public ListNode(Object data, ListNode next) {
this.data = data;
this.next = next;
this.testLL = null;
}
// for nodes that are only head/tails with a linked list extending outward
public ListNode(Object data, LinkedList testLL) {
this.data = data;
this.next = null;
this.testLL = testLL;
}
// for nodes in the middle with a linked list extending outward
public ListNode(Object data, ListNode next, LinkedList testLL) {
this.data = data;
this.next = next;
this.testLL = testLL;
}
}
链表代码：
public class LinkedList {
private ListNode head;
private ListNode tail;
private Comparator comparator;
private int count = 0;
private LinkedList test;
public LinkedList(Comparator comparator) {
head = tail = null;
this.comparator = comparator;
}
public boolean isEmpty() {
return (head==null);
}
public void addToHead(Object item) {
count++;
if (isEmpty()) {
head = tail = new ListNode(item, test);
} else {
head = new ListNode(item, head, test);
}
}
public void addToTail(Object item) {
count++;
if (isEmpty()) {
head = tail = new ListNode(item, test);
} else {
tail.next = new ListNode(item, test);
tail = tail.next;
}
}
public Object removeFromHead() throws EmptyListException {
Object item = null;
if (isEmpty()) {
throw new EmptyListException();
}
item = head.data;
if (head == tail) // there's only one single node
head = tail = null;
else
head = head.next;
count--;
return item;
}
public Object removeFromTail() throws EmptyListException {
if (isEmpty()) {
throw new EmptyListException();
}
Object item = tail.data;
if (head == tail) { // there is only one node
head = tail = null;
return item;
}
ListNode current = head;
while (current.next != tail)
current = current.next;
tail = current;
tail.next = null;
count--;
return item;
}
// removes duplicate nodes
public void removeDuplicate() throws EmptyListException {
ListNode current = head;
ListNode checker = current.next;
iterateLL:
while (current.next != null) {
// start from head, check data one by one until the data is not the same,
// then go to that data and connect it to current
checkRepeated:
while(checker != null){
if(checker.data.equals(current.data)){
if(checker.next == null){
current.next = null;
break iterateLL;
}
else{
checker = checker.next;
continue checkRepeated;
}
}
else{
current.next = checker;
current = current.next;
checker = current.next;
break checkRepeated;
}
}
}
}
public String toString1() { // original toString method, will not be changed, for backup if anything messed up
String s = "[ ";
ListNode current = head;
while (current != null) {
s += current.data + " ";
current = current.next;
}
return s + "]";
}
public String toString2() {
ListNode current = head;
String s = "\nIdentifiers found:";
while (current != null) {
// start from head, check data one by one until the data is not the same,
// then go to that data and input it into String s
s += "\n" + current.data + current.testLL.toString1();
current = current.next;
}
return s;
}
public int getCount(){
return count;
}
public void insertInOrder (Object item) {
if (isEmpty()) {
head = tail = new ListNode (item);
count++;
} else {
if (comparator.isGreaterThanOrEqualTo(head.data, item)) {
addToHead(item);
} else if (comparator.isLessThanOrEqualTo(tail.data, item)) {
addToTail(item);
} else {
// insert in the middle
ListNode current = head;
while (current.next != null) {
if (comparator.isGreaterThanOrEqualTo(current.next.data, item)) {
ListNode newNode = new ListNode(item, test);
newNode.next = current.next;
current.next = newNode;
count++;
return;
}
current = current.next;
}
}
}
}
public void removeItem (Object item) throws ItemNotFoundException {
if (isEmpty()) {
throw new ItemNotFoundException();
}
if (comparator.isEqualTo(head.data, item))
removeFromHead();
else if (comparator.isEqualTo(tail.data, item))
removeFromTail();
else {
// remove a node in the middle
ListNode current = head;
while (current.next != null) {
if (comparator.isEqualTo(current.next.data, item)) {
current.next = current.next.next;
count--;
return;
}
current = current.next;
}
throw new ItemNotFoundException();
}
}
}
异常是自定义异常，比较器用于使链表排序
toString2简而言之：是的，如果一个节点可以包含任何类型的对象，那么该类型可以是
LinkedList您可能会考虑的一些改进：
ObjectgetHead()getTail()