利用JAVA实现以下内容

Question

1.实现循环单链表类CirSinglyList增加的以下成员方法：
CirSinglyList difference(SinglyList list) //返回差集，list和返回值深拷贝
2.实现循环双链表类CirDoublyList增加的以下成员方法：
void replaceAll(DoublyListpattern, DoublyListlist) //替换所有匹配的子表为list（深拷贝）

求完整代码😍

Answer 1

1. 在Java中实现循环单链表类CirSinglyList增加的以下成员方法：

   public class CirSinglyList<T> {
    private Node<T> head; // 头结点
   
    // 节点类
    private static class Node<T> {
        T data; // 数据
        Node<T> next; // 指向下一个节点的指针
   
        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }
   
    // 返回差集，list和返回值深拷贝
    public CirSinglyList<T> difference(SinglyList<T> list) {
        CirSinglyList<T> result = new CirSinglyList<>();
        Node<T> p = head;
        do {
            boolean found = false;
            Node<T> q = list.head;
            do {
                if (p.data.equals(q.data)) {
                    found = true;
                    break;
                }
                q = q.next;
            } while (q != list.head);
   
            if (!found) {
                result.insertTail(p.data);
            }
            p = p.next;
        } while (p != head);
   
        return result;
    }
   
    // 插入节点到链表尾部
    public void insertTail(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
            head.next = head;
        } else {
            Node<T> p = head;
            while (p.next != head) {
                p = p.next;
            }
            p.next = newNode;
            newNode.next = head;
        }
    }
   }
   

2. 在Java中实现循环双链表类CirDoublyList增加的以下成员方法：

   public class CirDoublyList<T> {
    private Node<T> head; // 头结点
   
    // 节点类
    private static class Node<T> {
        T data; // 数据
        Node<T> prev; // 指向前一个节点的指针
        Node<T> next; // 指向下一个节点的指针
   
        Node(T data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }
   
    // 替换所有匹配的子表为list（深拷贝）
    public void replaceAll(DoublyList<T> pattern, DoublyList<T> list) {
        Node<T> p = head;
        while (p != null) {
            if (isMatch(p, pattern.head)) {
                Node<T> q = list.head;
                while (q.next != null) {
                    q = q.next;
                }
                Node<T> newNode = deepCopy(q);
                if (p.prev != null) {
                    p.prev.next = newNode;
                } else {
                    head = newNode;
                }
                newNode.prev = p.prev;
                newNode.next = p.next;
                if (p.next != null) {
                    p.next.prev = newNode;
                }
            }
            p = p.next;
        }
    }
   
    // 判断当前节点及后续节点是否与pattern匹配
    private boolean isMatch(Node<T> p, Node<T> pattern) {
        Node<T> q = pattern;
        while (q != null && p != null) {
            if (!p.data.equals(q.data)) {
                return false;
            }
            p = p.next;
            q = q.next;
        }
        return q == null;
    }
   
    // 深拷贝节点
    private Node<T> deepCopy(Node<T> node) {
        Node<T> newNode = new Node<>(node.data);
        if (node.next != null) {
            newNode.next = deepCopy(node.next);
            newNode.next.prev = newNode;
        }
        return newNode;
    }
   }