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

Commit64df5a2

Browse files
authored
Update 0148-sort-list.java
This code is the implementation of the merge sort, as explained in the video
1 parentfe98604 commit64df5a2

File tree

1 file changed

+54
-13
lines changed

1 file changed

+54
-13
lines changed

‎java/0148-sort-list.java

Lines changed: 54 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,61 @@
1+
// Applying Merge Sort on the Linked List
2+
3+
/**
4+
* Definition for singly-linked list.
5+
* public class ListNode {
6+
* int val;
7+
* ListNode next;
8+
* ListNode() {}
9+
* ListNode(int val) { this.val = val; }
10+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
11+
* }
12+
*/
113
classSolution {
14+
// Merge Sort Implementation
15+
publicListNodegetMid(ListNodehead){
16+
ListNodeslow=head,fast=head.next;
17+
while(fast !=null &&fast.next !=null){
18+
fast =fast.next.next;
19+
slow =slow.next;
20+
}
21+
returnslow;
22+
}
23+
publicListNodemerge(ListNodeleft,ListNoderight){
24+
ListNodedummy =newListNode();
25+
ListNodetail =dummy;
26+
27+
while(left !=null &&right !=null){
28+
if(left.val <right.val){
29+
tail.next =left;
30+
left =left.next;
31+
}else{
32+
tail.next =right;
33+
right =right.next;
34+
}
35+
tail =tail.next;
36+
}
37+
if(left !=null){
38+
tail.next =left;
39+
}
40+
if(right !=null){
41+
tail.next =right;
42+
}
43+
returndummy.next;
44+
}
245
publicListNodesortList(ListNodehead) {
346
if(head ==null ||head.next ==null){
447
returnhead;
548
}
6-
PriorityQueue<Integer>queue =newPriorityQueue<>();
7-
ListNodetemp =head;
8-
while(temp.next!=null){
9-
queue.add(temp.val);
10-
temp =temp.next;
11-
}
12-
queue.add(temp.val);
13-
temp =head;
14-
while(!queue.isEmpty()){
15-
temp.val =queue.poll();
16-
temp =temp.next;
17-
}
18-
returnhead;
49+
50+
// Split the list in 2 halfs
51+
ListNodeleft =head;
52+
ListNoderight =getMid(head);
53+
ListNodetmp =right.next;
54+
right.next =null;
55+
right =tmp;
56+
57+
left =sortList(left);
58+
right =sortList(right);
59+
returnmerge(left,right);
1960
}
2061
}

0 commit comments

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