FilesExpand file tree

 master

/

MergeSortedSinglyLinkedList.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

51 lines (45 loc) · 1.34 KB

 master

/

MergeSortedSinglyLinkedList.java

Top

File metadata and controls

• Code
• Blame

51 lines (45 loc) · 1.34 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package DataStructures.Lists;

public class MergeSortedSinglyLinkedList extends SinglyLinkedList {

public static void main(String[] args) {

SinglyLinkedList listA = new SinglyLinkedList();

SinglyLinkedList listB = new SinglyLinkedList();

for (int i = 2; i <= 10; i += 2) {

listA.insert(i);

listB.insert(i - 1);

}

assert listA.toString().equals("2->4->6->8->10");

assert listB.toString().equals("1->3->5->7->9");

assert merge(listA, listB).toString().equals("1->2->3->4->5->6->7->8->9->10");

}

/**

* Merge two sorted SingleLinkedList

*

* @param listA the first sorted list

* @param listB the second sored list

* @return merged sorted list

*/

public static SinglyLinkedList merge(SinglyLinkedList listA, SinglyLinkedList listB) {

Node headA = listA.getHead();

Node headB = listB.getHead();

int size = listA.size() + listB.size();

Node head = new Node();

Node tail = head;

while (headA != null && headB != null) {

if (headA.value <= headB.value) {

tail.next = headA;

headA = headA.next;

} else {

tail.next = headB;

headB = headB.next;

}

tail = tail.next;

}

if (headA == null) {

tail.next = headB;

}

if (headB == null) {

tail.next = headA;

}

return new SinglyLinkedList(head.next, size);

}

}