Intersection of two Sorted Linked List in Kotlin

by

To find the intersection of two sorted linked lists, you can use a two-pointer approach where you traverse both linked lists simultaneously and compare the values at each node. Here’s a step-by-step guide:

  1. Initialize two pointers, one for each linked list, to point to the head of each list.
  2. Traverse both lists simultaneously using the two pointers until you reach the end of one of the lists or until you find a common node.
  3. At each step, compare the values at the current nodes of both linked lists.
  4. If the values are equal, you have found an intersection node. Add this node to a new linked list that you will create to store the intersection nodes.
  5. If the value in one of the linked lists is less than the other, move the pointer for that linked list to the next node.
  6. Repeat steps 3-5 until you have traversed both linked lists completely.
  7. Return the head of the new linked list containing the intersection nodes.

Kotlin code for finding the intersection of two sorted linked lists:

Kotlin
class ListNode(var `val`: Int) {
    var next: ListNode? = null
}
fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
    var p1 = headA
    var p2 = headB
    var intersect: ListNode? = null
    var tail: ListNode? = null
    while (p1 != null && p2 != null) {
        if (p1.`val` == p2.`val`) {
            val newNode = ListNode(p1.`val`)
            if (intersect == null) {
                intersect = newNode
                tail = newNode
            } else {
                tail?.next = newNode
                tail = tail?.next
            }
            p1 = p1.next
            p2 = p2.next
        } else if (p1.`val` < p2.`val`) {
            p1 = p1.next
        } else {
            p2 = p2.next
        }
    }
    return intersect
}
fun main() {
    // create linked list 1: 1 -> 2 -> 4 -> 5 -> 6
    val node1 = ListNode(1)
    val node2 = ListNode(2)
    val node3 = ListNode(4)
    val node4 = ListNode(5)
    val node5 = ListNode(6)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    // create linked list 2: 2 -> 5 -> 6 -> 8
    val node6 = ListNode(2)
    val node7 = ListNode(5)
    val node8 = ListNode(6)
    val node9 = ListNode(8)
    node6.next = node7
    node7.next = node8
    node8.next = node9
    // find intersection of linked lists 1 and 2
    val intersection = getIntersectionNode(node1, node6)
    // print the values of the intersection nodes
    var p = intersection
    while (p != null) {
        print("${p.`val`} ")
        p = p.next
    }
    // expected output: 2 5 6 
}
  1. The function takes two linked lists (headA and headB) as input, both of which are sorted in ascending order.
  2. Two pointers (p1 and p2) are initialized to the head of each list. Also, two other pointers (intersect and tail) are initialized to null, which will be used to store the intersection nodes.
  3. A loop is started, which will continue until either of the pointers (p1 or p2) reaches the end of its linked list.
  4. At each step of the loop, the values at the current nodes of both linked lists are compared. If they are equal, it means we have found an intersection node, which needs to be added to the new linked list.
  5. If intersect is null, it means this is the first intersection node that we have found, so we create a new linked list with this node and set tail to point to it. Otherwise, we append the new intersection node to the end of the existing linked list and update tail to point to the new tail node.
  6. We move both pointers (p1 and p2) to the next node, as we have already processed the current nodes.
  7. If the value at p1 is less than the value at p2, it means the node in the first linked list is smaller, so we move p1 to the next node. Similarly, if the value at p2 is less than the value at p1, we move p2 to the next node.
  8. Once the loop is completed, we return the head of the new linked list (intersect).

Time complexity:

  • The time complexity of the function is O(min(m, n)), where m and n are the lengths of the two input linked lists. This is because the function iterates through both linked lists in a single loop, and at each iteration, it compares the values of two nodes and moves the pointers to the next nodes in one or both linked lists. Since the function processes each node at most once, the time complexity is proportional to the length of the smaller linked list.

Space complexity:

  • The space complexity of the function is O(k), where k is the number of intersection nodes between the two input linked lists. This is because the function creates a new linked list to store the intersection nodes, and the length of the new linked list is at most the number of intersection nodes. Therefore, the space complexity is proportional to the size of the output, which is the intersection linked list.

Leave a Comment