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

Commitca761d8

Browse files
authored
feat: add MergeTwoSortedLinkedLIsts algorithms (TheAlgorithms#1442)
* feat: add mergeTwoSortedLinkedLIsts algorithms* remove class and unnecessary functionchange the function params and return value from Node to LinkedList.
1 parent3823ede commitca761d8

File tree

2 files changed

+84
-0
lines changed

2 files changed

+84
-0
lines changed
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
import{LinkedList}from'./SinglyLinkedList.js'
2+
/**
3+
* A LinkedList-based solution for merging two sorted linked lists into one sorted list.
4+
*
5+
*@param {LinkedList} list1 - The the first sorted linked list.
6+
*@param {LinkedList} list2 - The second sorted linked list.
7+
*@returns {LinkedList} - The merged sorted linked list.
8+
*
9+
*@example
10+
* const list1 = new LinkedList([1,2,4]);
11+
*
12+
* const list2 = new LinkedList([1,3,4]);
13+
*
14+
* const result = mergeLinkedLists(list1, list2);
15+
* // Returns the merged linked list representing 1 -> 1 -> 2 -> 3 -> 4 -> 4
16+
*/
17+
18+
functionmergeLinkedLists(list1,list2){
19+
constmergedList=newLinkedList()
20+
21+
letcurrent1=list1.headNode
22+
letcurrent2=list2.headNode
23+
24+
while(current1||current2){
25+
if(!current1){
26+
mergedList.addLast(current2.data)
27+
current2=current2.next
28+
}elseif(!current2){
29+
mergedList.addLast(current1.data)
30+
current1=current1.next
31+
}else{
32+
if(current1.data<current2.data){
33+
mergedList.addLast(current1.data)
34+
current1=current1.next
35+
}else{
36+
mergedList.addLast(current2.data)
37+
current2=current2.next
38+
}
39+
}
40+
}
41+
42+
returnmergedList
43+
}
44+
45+
export{mergeLinkedLists}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
import{expect}from'vitest'
2+
import{mergeLinkedLists}from'../MergeTwoSortedLinkedLists.js'
3+
import{LinkedList}from'../SinglyLinkedList.js'
4+
5+
describe('MergeTwoSortedLinkedLists',()=>{
6+
it('Merges two sorted linked lists',()=>{
7+
constlist1=newLinkedList([1,2,4])
8+
9+
constlist2=newLinkedList([1,3,4])
10+
11+
constexpectedResult=newLinkedList([1,1,2,3,4,4])
12+
13+
constresult=mergeLinkedLists(list1,list2)
14+
15+
expect(result).toEqual(expectedResult)
16+
})
17+
18+
it('Merges two empty linked lists',()=>{
19+
constlist1=newLinkedList()
20+
constlist2=newLinkedList()
21+
22+
constexpectedResult=newLinkedList()
23+
24+
constresult=mergeLinkedLists(list1,list2)
25+
26+
expect(result).toEqual(expectedResult)
27+
})
28+
29+
it('Merges one empty linked list with a non-empty one',()=>{
30+
constlist1=newLinkedList()
31+
constlist2=newLinkedList([1])
32+
33+
constexpectedResult=newLinkedList([1])
34+
35+
constresult=mergeLinkedLists(list1,list2)
36+
37+
expect(result).toEqual(expectedResult)
38+
})
39+
})

0 commit comments

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