How to find find pairs with given sum in doubly linked list

[Question]: Given a sorted doubly linked list of positive distinct elements, Find pairs in a doubly-linked list whose sum is equal to given value k, without using any extra space? 

#Approach. Using two pointer

  1. Initialize two pointer variables, Initialize first with the start of the doubly linked list i.e; firstPointer=head and initialize second with the last node of the doubly linked list i.e; secondPointer=lastNode.
  2. If current sum of first and second is less than k, then we move first in forward direction. If current sum of first and second element is greater than k, then we move second in backward direction.
  3. Loop termination conditions are also different from arrays. The loop terminates when two pointers cross each other (secondPointer.next = firstPointer), or they become the same (firstPointer == secondPointer).
func pairSumEqualK( _ head: DoublyLinkedListNode<Int>?, _ k: Int) {
    var firstPointer = head, secondPointer = head
    while secondPointer?.next != nil {
        secondPointer = secondPointer?.next
    }
    
    while firstPointer !== secondPointer && secondPointer?.next !== firstPointer {
        // pair found
        if firstPointer!.item + secondPointer!.item == k {
            print("pointers--- > ",firstPointer!.item, secondPointer!.item)// Output 1,4, 2,3
            // move first in forward direction
            firstPointer = firstPointer?.next
            // move second in backward direction
            secondPointer = secondPointer?.previous
            
        } else {
            if  firstPointer!.item + secondPointer!.item < k {
                firstPointer = firstPointer?.next
            } else {
                secondPointer = secondPointer?.previous
            }
        }
    }
}

var pairLinkedList = DoublyLinkedList<Int>()
pairLinkedList = [1,2,3,4,9]

pairSumEqualK(pairLinkedList.head, 5)// Output printed in function

Leave a Comment

Your email address will not be published. Required fields are marked *