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;}
}

附言

如果上述代码看不懂的话，建议先把这两道题刷一下
148. 排序链表 - 力扣（LeetCode）
109. 有序链表转换二叉搜索树 - 力扣（LeetCode）