PROBLEM DESCRIPTION
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
leetcode
SOLUTION
First we get the center of the list. We break it into two linked lists by setting the next pointer of the middle element to null. Before doing this, we will need to “save” the head of the second half of the list in some temporary variable. Now, we can recursively call our function to sort the first half and second half of the linked list. Finally, the result needs to the merged of the first half and second half of these lists. We can do this using a separate method.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// Main function to sort a linked list in ascending order.
public ListNode sortList(ListNode head) {
// Base cases: If the list is empty or has only one node, return as it's already sorted.
if (head == null || head.next == null) {
return head;
}
// Find the center node of the linked list.
ListNode centerNode = getCenter(head);
// Split the list into two halves.
ListNode head2 = centerNode.next;
centerNode.next = null; //IMPORTANT: Break the link between the two halves.
// Recursively sort the first half and the second half of the list.
ListNode firstHalf = sortList(head);
ListNode secondHalf = sortList(head2);
// Merge the sorted halves back together.
return mergeSortedLists(firstHalf, secondHalf);
}
// Function to merge two sorted linked lists.
public ListNode mergeSortedLists(ListNode head1, ListNode head2) {
// Base cases: If either list is null, return the other list.
if (head1 == null) return head2;
if (head2 == null) return head1;
// Compare the values of the current nodes and merge accordingly.
// If the value of head1 is lesser, it needs to come before any other element
if (head1.val <= head2.val) {
// Store this head and set its next to null
ListNode tempHead = head1.next;
head1.next = null;
// Recursively merge the remaining elements, and this will be the new next for the head1 node
head1.next = mergeSortedLists(tempHead, head2);
return head1;
//otherwise, do the same thing for head2 node because that has a lesser value
} else {
ListNode tempHead = head2.next;
head2.next = null;
// Recursively merge the remaining elements.
head2.next = mergeSortedLists(head1, tempHead);
return head2;
}
}
// Function to find the center node of a linked list.
public ListNode getCenter(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// Use the slow and fast pointer technique to find the center.
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}