Java实现循环双向链表时如何正确删除指定节点?
Java循环双向链表节点删除问题
我正在尝试编写程序,实现循环双向链表的两个功能:正向移动指定步数、反向移动指定步数。按照规则:如果两次移动最终停在对应同一数值的节点上,该数值判定为「有效(worthy)」,需要从链表中移除;如果两次移动没有停在同一个节点上,两个节点都判定为「无效(unworthy)」,同样需要从链表中移除。目前我已经写完了指定步数的正向、反向移动方法,但在删除判定完成的节点时遇到了问题,以下是我目前的代码:
自定义链表实现代码
import java.util.Arrays; public class LinkedList { private Node head; private Node end; LinkedList(){ head = end = null; } public void addAtStart(int x){ if (head == null) { Node new_node = new Node(x); new_node.data = x; new_node.next = new_node.prev = new_node; head = new_node; } else if (head != null) { Node last = head.prev; Node new_node = new Node(x); new_node.data = x; new_node.next = head; head.prev = new_node; new_node.prev = last; last.next = new_node; } } public void printOutput(int N, int k, int m){ System.out.println("Output" + "\n" + "------" + "\n"); printCandidates(N,k,m); } public void printCandidates(int N, int k, int m){ int unworthy[] = new int[N]; int worthy[] = new int[N]; int count = 0; int run = 0; Node temp = head; do { if (forwards(k) == backwards(m)){ // 放入有效列表并从链表删除 worthy[count] = forwards(k); count += 1; System.out.println("hello"); deleteElement(forwards(k)); } else if (forwards(k) != backwards(m)){ // 放入无效列表并从链表删除 unworthy[run] = forwards(k); unworthy[run+1] = backwards(m); run += 2; System.out.println("goodbye"); deleteElement(forwards(k)); deleteElement(backwards(m)); } } while (temp != null); System.out.println("落选候选人"); System.out.println(Arrays.toString(unworthy)); System.out.println("有效候选人"); System.out.println(Arrays.toString(worthy)); } int forwards(int k){ int run = 0; int x = 0; Node temp = head; while (temp.next != head){ if(run == k){ x = temp.data; } temp = temp.next; run += 1; } return x; } int backwards(int m){ int run = 0; int x = 0; Node temp = head; Node last = head.prev; temp = last; while (temp.next != head){ if(run == m){ x = temp.data; } temp = temp.next; run += 1; } return x; } public void deleteElement(int elementToBeDeleted){ Node temp = head; while (temp.next != head){ if(temp.data == elementToBeDeleted){ temp.setNext(temp.next); } temp = temp.next; } } }
驱动类代码
public class Program2 { public static void main(String[] args) { LinkedList ll = new LinkedList(); for (int i = 1; i < 11; i++){ ll.addAtStart(i); } int N = 10; int k = 4; int m = 3; System.out.println("N = " + N + ", " + "k = " + k + ", " + "m = " + m + "\n"); ll.printOutput(N,k,m); } }
节点类代码
public class Node { public int data; public Node next; public Node prev; // 初始化节点数据的构造方法 public Node(int data){ this.data = data; } // 设置后继节点地址 public void setNext(Node temp) { this.next = temp; } // 获取后继节点地址 public Node getNext(){ return this.next; } public Node getPrev(){ return this.prev; } public void setPrev(Node temp) { this.prev = temp; } // 获取当前节点数据 public int getData(){ return this.data; } }
补充说明
本次练习要求自行实现链表类,所以我没有调用Java内置的链表类,选择了手动实现。
内容的提问来源于stack exchange,提问作者Megan
相关产品推荐
相关产品推荐

