[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
- 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.
- 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.
- 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