将循环双链表的代码修改为循环单链表的代码,方法不变动太大,可以按照以下方式进行修改:
public class CirSinglyList2<T> {
public Node<T> head;
public CirSinglyList2() {
this.head = null;
}
public boolean isEmpty() {
return head == null;
}
public String toString() {
if (isEmpty()) {
return "CirSinglyList2()";
}
StringBuilder sb = new StringBuilder();
sb.append("CirSinglyList2(");
Node<T> p = head;
while (p.next != head) {
sb.append(p.data.toString()).append(",");
p = p.next;
}
sb.append(p.data.toString());
sb.append(")");
return sb.toString();
}
public Node<T> insert(int i, T x) {
if (x == null || i < 0) {
return null;
}
if (i == 0 || isEmpty()) { // 插入头节点位置
Node<T> q = new Node<>(x, head);
if (head == null) { // 当前为空列表,形成闭环
q.next = q;
} else { // 非空列表,在头节点插入新节点
Node<T> rear = head; // 查找尾节点
while (rear.next != head) {
rear = rear.next;
}
rear.next = q; // 将尾节点连接到新节点
q.next = head; // 新节点连接到原头节点
}
head = q; // 更新头指针为新节点
return q;
}
int j = 0;
Node<T> p = head; // 查找插入位置的前驱节点
while (p.next != head && j < i - 1) {
p = p.next;
j++;
}
if (j == i - 1 || p.next == head) { // 插入位置有效,执行插入操作
Node<T> q = new Node<>(x, p.next);
if (p.next == head) { // 在尾节点后面插入新节点
p.next = q;
q.next = head;
} else { // 在中间位置插入新节点
q.next = p.next;
p.next = q;
}
return q;
} else {
return null; // 插入位置无效,返回null
}
}
public Node<T> insert(T x) {
if (x == null) {
return null;
}
if (isEmpty()) { // 当前为空列表,形成闭环的单节点循环链表
Node<T> node = new Node<>(x);
node.next = node; // 节点自己指向自己
head = node; // 更新头指针为新节点
return node;
} else { // 非空列表,在尾部插入新节点
Node<T> rear = head; // 查找尾节点
while (rear.next != head) {
rear = rear.next;
}
Node<T> newNode=new Node<>(x,head);
rear.next=newNode;
return newNode;
}
}
public void addAll(CirSinglyList2<T> list) {
if (list.isEmpty()) {
return;
}
if (isEmpty()) {
head = list.head; // 将被添加列表的头节点作为新列表的头节点
head.next = head; // 形成闭环
} else {
Node<T> rear = head; // 查找当前列表的尾节点
while (rear.next != head) {
rear = rear.next;
}
Node<T> p = list.head; // 遍历被添加列表的节点
while (p.next != list.head) { // 复制每个被添加列表节点并插入到当前列表中
Node<T> newNode=new Node<>(p.data,head);
rear.next=newNode;
rear = newNode;
p=p.next;
}
Node<T> newNode=new Node<>(p.data,head);
rear.next=newNode;
rear=newNode;
}
rear.next=head; // 将尾节点与头节点连接形成闭环
}
public static void main(String[] args) {
CirSinglyList2<Integer> list1 = new CirSinglyList2<>();
CirSinglyList2<Integer> list2 = new CirSinglyList2<>();
for(int i=6; i<=10; i++)
list1.insert(i);
for(int i=11; i<=15; i++)
list2.insert(i);
System.out.println(list1.toString());
System.out.println(list2.toString());
list1.addAll(list2);
System.out.println(list1.toString());
}
}
class Node<T>{
public T data;
public Node<T> next;
public Node(){
this.data=null;
this.next=null;
}
public Node(T data){
this.data=data;
this.next=null;
}
public Node(T data,Node<T> next){
this.data=data;
this.next=next;
}
}
这样就完成了将循环双链表的代码修改为循环单链表的代码,并且保持方法不变动太大。
内容由零声教学AI助手提供,问题来源于学员提问




