Merge Two Linked List

Introduction

Merging two linked lists is a common problem in data structures. It helps us understand pointers, traversal, and efficient data handling.

---

Problem Statement

Given two sorted linked lists, merge them into a single sorted linked list and return the merged list.

---

Approach

We can solve this problem using the following steps:

1. Create a dummy node to store the result
2. Compare nodes of both linked lists
3. Attach the smaller node to the result
4. Move the pointer forward
5. Repeat until one list becomes empty
6. Attach the remaining elements

---

Python Code

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    tail = dummy

    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    # Attach remaining nodes
    if l1:
        tail.next = l1
    else:
        tail.next = l2

    return dummy.next

## Example:

  List1 : 1-> 3-> 5
  List2 : 2-> 4-> 6

## output:

1-> 2-> 3-> 4-> 5-> 6