| 37 | |
| 38 | # Function to merge two sorted linked list. |
| 39 | def mergeLists(head1, head2): |
| 40 | # create a temp node NULL |
| 41 | temp = None |
| 42 | |
| 43 | # List1 is empty then return List2 |
| 44 | if head1 is None: |
| 45 | return head2 |
| 46 | |
| 47 | # if List2 is empty then return List1 |
| 48 | if head2 is None: |
| 49 | return head1 |
| 50 | |
| 51 | # If List1's data is smaller or |
| 52 | # equal to List2's data |
| 53 | if head1.data <= head2.data: |
| 54 | # assign temp to List1's data |
| 55 | temp = head1 |
| 56 | |
| 57 | # Again check List1's data is smaller or equal List2's |
| 58 | # data and call mergeLists function. |
| 59 | temp.next = mergeLists(head1.next, head2) |
| 60 | |
| 61 | else: |
| 62 | # If List2's data is greater than or equal List1's |
| 63 | # data assign temp to head2 |
| 64 | temp = head2 |
| 65 | |
| 66 | # Again check List2's data is greater or equal List's |
| 67 | # data and call mergeLists function. |
| 68 | temp.next = mergeLists(head1, head2.next) |
| 69 | |
| 70 | # return the temp list. |
| 71 | return temp |
| 72 | |
| 73 | |
| 74 | # Driver Function |