單連結清單如何設計在 O(1)時間删除單連結清單節點

題目描述

提供單連結清單的首節點和删除節點，定義一個方法在 O(1)時間删除該節點。

思路分析

節點類

@Data
public class Node {
    /**
     * 用于儲存節點中的資料
     */
    private Object data;
    /**
     * 用于儲存下一個節點的位址值
     */
    private Node next;

    public Node(Object data) {
        this.data = data;
    }

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}      

實作類

package day04;

/**
 * @Author yqq
 * @Date 2022/05/07 12:32
 * @Version 1.0
 */
public class Test01 {
    public static void main(String[] args) {
        Node lastNode = new Node(55);
        Node node4 = new Node(44,lastNode);
        Node node3 = new Node(33,node4);
        Node node2 = new Node(22,node3);
        Node headNode = new Node(11,node2);
        Node node = delete(headNode, lastNode);
        print(node);
    }

    /**
     * 實作單連結清單的周遊操作
     * @param headNode
     */
    public static void print(Node headNode){
        //定義一個臨時節點，用于輔助單連結清單的周遊操作
        Node tempNode = headNode;
        //定義一個循環，泳用于實作單連結清單的周遊操作
        while (tempNode != null){
            //輸出tempNode中data值
            System.out.println(tempNode.getData());
            //讓tempNode指向下一個節點
            tempNode = tempNode.getNext();
        }
    }

    /**
     * 在O(1)時間删除單連結清單節點
     * @param headNode 首節點
     * @param delNode 删除節點
     * @return
     */
    public static Node delete(Node headNode,Node delNode){
        //處理headNode為null和delNode為null的情況
        if (headNode == null || delNode == null)
            throw new NullPointerException("headNode 或 delNode為null");
        //處理删除節點在開頭的情況
        if (headNode == delNode){
            //獲得删除節點的後一個節點
            Node nextNode = headNode.getNext();
            //設定headNode的next為null
            headNode.setNext(null);
            //傳回删除節點的後單連結清單的首節點
            return nextNode;
        }
        //處理删除節點在結尾的情況
        else if (delNode.getNext() == null){
            //獲得删除節點的前一個節點
            //定義一個臨時節點，用于輔助周遊連結清單
            Node tempNode = headNode;
            //定義一個循環，用于找到尾結點的前一個節點
            while (tempNode.getNext() != delNode){
                //讓tempNode指向它的下一個節點
                tempNode = tempNode.getNext();
            }
            //設定tempNode的next為null
            tempNode.setNext(null);
            //傳回删除節點後單連結清單的首節點
            return headNode;
        }
        //處理删除節點在中間任意位置的情況
        else {
            //獲得删除節點的後一個節點
            Node nextNode = delNode.getNext();
            //把nextNode中儲存的資料指派給删除節點
            delNode.setData(nextNode.getData());
            //從單連結清單中删除nextNode
            //設定delNode的next值為nextNode的下一個節點
            delNode.setNext(nextNode.getNext());
            //設定nextNode的next為null
            nextNode.setNext(null);
            //傳回删除節點後單連結清單的首節點
            return headNode;
        }
    }
}