Merge Two Sorted Linked List in Kotlin

by

To merge two sorted linked lists, you can follow these steps:

  1. Initialize a new empty linked list.
  2. Set two pointers to the heads of the two input linked lists.
  3. Compare the values of the two nodes pointed by the two pointers. Append the smaller one to the new linked list and move the corresponding pointer to the next node.
  4. Repeat step 3 until one of the pointers reaches the end of the linked list.
  5. Append the rest of the nodes from the non-empty linked list to the new linked list.
  6. Return the head of the new linked list.
class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
    // Step 1
    val dummy = ListNode(-1)
    var current: ListNode? = dummy

    // Step 2
    var p1 = l1
    var p2 = l2

    // Step 3
    while (p1 != null && p2 != null) {
        if (p1.`val` < p2.`val`) {
            current?.next = p1
            p1 = p1.next
        } else {
            current?.next = p2
            p2 = p2.next
        }
        current = current?.next
    }

    // Step 4
    if (p1 != null) {
        current?.next = p1
    } else {
        current?.next = p2
    }

    // Step 5
    return dummy.next
}
  1. Create a new ListNode called dummy with a value of -1. This node will act as the head of the merged linked list.
  2. Initialize two pointers p1 and p2 to the heads of the input linked lists l1 and l2.
  3. Iterate through both linked lists as long as both pointers p1 and p2 are not null. At each iteration, compare the values of p1 and p2. If p1.val is less than p2.val, append p1 to the merged linked list by setting current.next to p1 and advancing p1 to its next node. Otherwise, append p2 to the merged linked list by setting current.next to p2 and advancing p2 to its next node. Finally, advance current to its next node.
  4. If one of the input linked lists (l1 or l2) still has nodes remaining, append the rest of those nodes to the merged linked list.
  5. Return the head of the merged linked list, which is the next node of the dummy node we created in Step 1.
class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
    // Step 1
    val dummy = ListNode(-1)
    var current: ListNode? = dummy

    // Step 2
    var p1 = l1
    var p2 = l2

    // Step 3
    while (p1 != null && p2 != null) {
        if (p1.`val` < p2.`val`) {
            current?.next = p1
            p1 = p1.next
        } else {
            current?.next = p2
            p2 = p2.next
        }
        current = current?.next
    }

    // Step 4
    if (p1 != null) {
        current?.next = p1
    } else {
        current?.next = p2
    }

    // Step 5
    return dummy.next
}

fun main() {
    // Example usage
    val l1 = ListNode(1).apply {
        next = ListNode(3).apply {
            next = ListNode(5)
        }
    }
    val l2 = ListNode(2).apply {
        next = ListNode(4).apply {
            next = ListNode(6)
        }
    }
    val mergedList = mergeTwoLists(l1, l2)
    var current: ListNode? = mergedList
    while (current != null) {
        print("${current.`val`} ")
        current = current.next
    }
    // Output: 1 2 3 4 5 6
}

In the main function, two example linked lists are created and passed to mergeTwoLists. The resulting merged linked list is printed to the console.

Output : 1 2 3 4 5 6

Leave a Comment