Leetcode148,109以及二者的合并 -＞ Tencent面试算法题

Leetcode148,109以及二者的合并 -＞ Tencent面试算法题 - 无序双向链表转BST

根源简述

这道题是腾讯在2024/8/30考的一道面试题，整体来说，难度不大，就是代码量稍稍有点儿大，让我们一起来看一下吧

题目描述

整数无序双向链表能否转BST（二叉搜索树），如果能，怎么转 (尽可能少的时间复杂度和空间复杂度)，如果不能为什么？

解题思路

这道题想都不用想，一定是能转的，要不然考你干啥，接下来就看怎么转
我们可以把这个题拆成两个部分
1.整数无序双向链表进行排序

2.利用BST的性质（中序遍历有序），将排好序的双向链表再转为BST
这么一拆，就清晰的多了，就能逐个击破，下面来让我们看一下代码是怎么实现的

代码实现

class ListNode {
    int val;
    ListNode prev;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class DoublyLinkedListToBST {
    // 将双向链表进行排序
    public ListNode sortDoublyLinkedList(ListNode head) {
        // 如果链表为空或只有一个节点，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 找到链表的中间节点
        ListNode middle = getMiddle(head);
        ListNode middleNext = middle.next;

        // 将链表从中间断开
        middle.next = null;
        if (middleNext!= null) {
            middleNext.prev = null;
        }

        // 递归排序左半部分链表
        ListNode left = sortDoublyLinkedList(head);
        // 递归排序右半部分链表
        ListNode right = sortDoublyLinkedList(middleNext);

        // 合并左右两个已排序的链表
        return merge(left, right);
    }

    // 找到链表的中间节点
    public ListNode getMiddle(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!= null && fast.next.next!= null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 合并两个已排序的链表
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyNode = new ListNode(0);
        ListNode cur = dummyNode;

        while (head1!= null && head2!= null) {
            if (head1.val <= head2.val) {
                cur.next = head1;
                head1.prev = cur;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2.prev = cur;
                head2 = head2.next;
            }
            cur = cur.next;
        }

        if (head1!= null) {
            cur.next = head1;
            head1.prev = cur;
        }

        if (head2!= null) {
            cur.next = head2;
            head2.prev = cur;
        }

        ListNode head = dummyNode.next;
        head.prev = null;
        return head;
    }

    // 将排好序的双向链表转为二叉搜索树
    ListNode head;
    public TreeNode sortedListToBST(ListNode head) {
        this.head = head;
        int n = getSize(head);
        return sortedListToBSTHelper(n);
    }

    public int getSize(ListNode head) {
        if (head == null) {
            return 0;
        }
        int count = 0;
        ListNode cur = head;
        while (cur!= null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public TreeNode sortedListToBSTHelper(int n) {
        if (n <= 0) {
            return null;
        }
        // 递归构建左子树
        TreeNode leftSubtree = sortedListToBSTHelper(n / 2);

        // 创建当前节点
        TreeNode root = new TreeNode(this.head.val);

        // 连接左子树
        root.left = leftSubtree;

        // 移动链表指针到下一个节点
        this.head = this.head.next;

        // 递归构建右子树
        TreeNode rightSubtree = sortedListToBSTHelper(n - n / 2 - 1);

        // 连接右子树
        root.right = rightSubtree;
        return root;
    }
}