Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit70b974c

Browse files
committed
add 86, 109, list
1 parent7e4ab5b commit70b974c

File tree

4 files changed

+111
-2
lines changed

4 files changed

+111
-2
lines changed

‎Hard/154-findMinimumInRotatedSortedArray-II.js‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
/**
22
* Similar to 153-findMinimumInRotatedSortedArray, and 81-searchRotatedSortedArrayII,
3-
* combile the solutions from these two.
4-
*
3+
* combile the solutions from these two. e.g. [1,1,1,3,1,1,1,1,1,1], or [1,1,1,1,1,1,1,3,1]
4+
*
55
*@param {number[]} nums
66
*@return {number}
77
*/
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* function ListNode(val) {
4+
* this.val = val;
5+
* this.next = null;
6+
* }
7+
*/
8+
/**
9+
* Definition for a binary tree node.
10+
* function TreeNode(val) {
11+
* this.val = val;
12+
* this.left = this.right = null;
13+
* }
14+
*/
15+
/**
16+
*@param {ListNode} head
17+
*@return {TreeNode}
18+
*/
19+
varsortedListToBST=function(head){
20+
if(!head)returnhead;
21+
varslow=head;
22+
varfast=head;
23+
varprev=null;
24+
25+
while(fast&&fast.next){
26+
fast=fast.next.next;
27+
prev=slow;
28+
slow=slow.next;
29+
}
30+
31+
varnode=newTreeNode(slow.val);
32+
// if prev is null, it means, slow and fast did not move, it means this half is done.
33+
// otherwise, prev is the end of the first half (left sub tree). And set prev.next = null.
34+
if(!prev){
35+
head=null;
36+
}else{
37+
prev.next=null;
38+
}
39+
40+
node.left=sortedListToBST(head);
41+
node.right=sortedListToBST(slow.next);
42+
43+
returnnode;
44+
};

‎Medium/86-partition-List.js‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* function ListNode(val) {
4+
* this.val = val;
5+
* this.next = null;
6+
* }
7+
*/
8+
/**
9+
*@param {ListNode} head
10+
*@param {number} x
11+
*@return {ListNode}
12+
*/
13+
varpartition=function(head,x){
14+
if(!head||!head.next)returnhead;
15+
varfirst=newListNode(null);
16+
first.next=head;
17+
varnewHead=first;
18+
while(first.next.val<x){
19+
first=first.next;
20+
if(!first.next)returnnewHead.next;
21+
}
22+
varsecond=first;
23+
while(second.next){
24+
while(second.next.val>=x){
25+
second=second.next;
26+
if(!second.next)returnnewHead.next;
27+
}
28+
varfirstNext=first.next;
29+
varsecondNext=second.next;
30+
first.next=second.next;
31+
second.next=secondNext.next;
32+
secondNext.next=firstNext;
33+
first=first.next;
34+
}
35+
36+
returnnewHead.next;
37+
};
38+
39+
// use two extra list, 1st list tracks node less than x,
40+
// 2nd list tracks nodes >= x
41+
// clean and concise
42+
varpartition=function(head,x){
43+
vardummy1=newListNode(null);
44+
vardummy2=newListNode(null);
45+
varcurr1=dummy1;
46+
varcurr2=dummy2;
47+
48+
while(head){
49+
if(head.val<x){
50+
curr1.next=head;
51+
curr1=curr1.next;
52+
}else{
53+
curr2.next=head;
54+
curr2=curr2.next;
55+
}
56+
57+
head=head.next;
58+
}
59+
60+
curr1.next=dummy2.next;
61+
curr2.next=null;
62+
returndummy1.next;
63+
};

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,7 @@
109109
*[80. Remove Duplicates from Sorted Array II](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/) -[Solution](./Medium/80-removeDuplicatesII.js)
110110
*[81. Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/) -[Solution](./Medium/81-searchRotatedSortedArrayII.js)
111111
*[82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) -[Solution](./Medium/82-removeDuplicatesListII.js)
112+
*[86. Partition List](https://leetcode.com/problems/partition-list/) -[Solution](./Medium/86-partition-List.js)
112113
*[89. Gray Code](https://leetcode.com/problems/gray-code/) -[Solution](./Medium/89-grayCode.js)
113114
*[90. Subsets II](https://leetcode.com/problems/subsets-ii/) -[Solution](./Medium/90-subsetsII.js)
114115
*[92. Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/) -[Solution](./Medium/92-reverseLinkedListII.js)
@@ -118,6 +119,7 @@
118119
*[98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) -[Solution](./Medium/98-validateBST.js)
119120
*[103. Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/) -[Solution](./Medium/103-BSTZigzagLevelTraversal.js)
120121
*[108. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/) -[Solution](./Medium/108-convertSortedArraytoBST.js)
122+
*[109. Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/) -[Solution](./Medium/109-convertSortedListToBST.js)
121123
*[113. Path Sum II](https://leetcode.com/problems/path-sum-ii/) -[Solution](./Medium/113-pathSumII.js)
122124
*[114. Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/) -[Solution](./Medium/114-flattenTree.js)
123125
*[116. Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/) -[Solution](./Medium/116-PopulatingNextRightPointersinEachNode.js)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp