Java中实现双向链表

一、目标

        最近项目中实现双向链表，同时转为满二叉树。

二、代码

        用java实现双向链表的代码如下：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
public class FullBinaryTree {
    public TreeNode createTree(int[] nums, int i) {
        if (i >= nums.length || nums[i] == -1) {
            return null;
        }
        TreeNode root = new TreeNode(nums[i]);
        root.left = createTree(nums, 2 * i + 1);
        root.right = createTree(nums, 2 * i + 2);
        return root;
    }
 
    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
 
class ListNode {
    int val;
    ListNode prev;
    ListNode next;
    ListNode(int x) { val = x; }
}
 
public class DoublyLinkedList {
    public ListNode createList(int[] nums) {
        ListNode dummy = new ListNode(-1);
        ListNode prev = dummy;
        for (int num : nums) {
            ListNode node = new ListNode(num);
            prev.next = node;
            node.prev = prev;
            prev = node;
        }
        return dummy.next;
    }
 
    public int find(ListNode head, int target) {
        ListNode curr = head;
        while (curr != null) {
            if (curr.val == target) {
                return curr.val;
            }
            curr = curr.next;
        }
        return -1;
    }
 
    public ListNode insert(ListNode head, int pos, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode curr = dummy;
        while (pos > 0) {
            curr = curr.next;
            pos--;
        }
        ListNode node = new ListNode(val);
        node.prev = curr;
        node.next = curr.next;
        if (curr.next != null) {
            curr.next.prev = node;
        }
        curr.next = node;
        return dummy.next;
    }
 
    public ListNode modify(ListNode head, int pos, int val) {
        ListNode curr = head;
        while (pos > 0) {
            curr = curr.next;
            pos--;
        }
        curr.val = val;
        return head;
    }
 
    public ListNode delete(ListNode head, int pos) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode curr = dummy;
        while (pos > 0) {
            curr = curr.next;
            pos--;
        }
        ListNode node = curr.next;
        if (node.next != null) {
            node.next.prev = curr;
        }
        curr.next = node.next;
        return dummy.next;
    }
 
    public TreeNode toFullBinaryTree(ListNode head) {
        if (head == null) {
            return null;
        }
        List<Integer> nums = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            nums.add(curr.val);
            curr = curr.next;
        }
        int[] arr = nums.stream().mapToInt(Integer::intValue).toArray();
        FullBinaryTree fbTree = new FullBinaryTree();
        return fbTree.createTree(arr, 0);
    }
}
 

在以上代码中，ListNode类表示双向链表中的节点，包含一个值和前后两个节点。DoublyLinkedList类中定义了六个方法，分别为：

• createList方法用于根据给定的整数数组创建一个双向链表；
• find方法用于在双向链表中查找目标元素，并返回其值；
• insert方法用于在双向链表中插入新节点；
• modify方法用于修改双向链表中的节点值；
• delete方法用于删除双向链表中的节点；
• toFullBinaryTree方法用于将双向链表转换为一棵满二叉树，并返回根节点。

具体实现见代码。