Given a sorted doubly linked list of positive distinct elements, the task is to find pairs in a doubly-linked list whose sum is equal to given value target.
 
Example 1:
Input:  
1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9
target = 7
Output: (1, 6), (2,5)
Explanation: We can see that there are two pairs 
(1, 6) and (2,5) with sum 7.
 
Example 2:
Input: 
1 <-> 5 <-> 6
target = 6
Output: (1,5)
Explanation: We can see that there is one pairs  (1, 5) with sum 6.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function findPairsWithGivenSum() which takes head node of the doubly linked list and an integer target as input parameter and returns an array of pairs. If there is no such pair return empty array.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= target <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Amortized analysis

Starter code: from typing import Optional





from typing import List



"""



Definition for singly Link List Node

class Node:

    def __init__(self,x):

        self.data=x

        self.next=None

        self.prev=None



You can also use the following for printing the link list.

displayList(node)

"""



class Solution:

    def findPairsWithGivenSum(self, target : int, head : Optional['Node']) -> List[List[int]]:

        # code here

        



Solutions:
from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		ans = []
		slow = head
		fast = head
		while fast.next is not None:
			fast = fast.next
		while slow.data < fast.data:
			if slow.data + fast.data == target:
				ans.append((slow.data, fast.data))
				slow = slow.next
				fast = fast.prev
			elif slow.data + fast.data < target:
				slow = slow.next
			else:
				fast = fast.prev
		return ans


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		d = dict()
		cur = head
		res = []
		while cur != None:
			if d.get(target - cur.data, -1) != -1:
				arr = [cur.data, target - cur.data]
				arr.sort()
				res.append(arr)
			d[cur.data] = 1
			cur = cur.next
		res.sort()
		return res


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		res = []
		start = head
		end = head
		while end.next:
			end = end.next
		while start.data < end.data:
			s = start.data + end.data
			if s == target:
				res.append([start.data, end.data])
				start = start.next
				end = end.prev
			elif s < target:
				start = start.next
			else:
				end = end.prev
		return res


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		high = head
		low = head
		temp = []
		while high.next != None:
			high = high.next
		while low.data < high.data:
			sum = low.data + high.data
			if sum > target:
				high = high.prev
			elif sum < target:
				low = low.next
			else:
				temp.append([low.data, high.data])
				low = low.next
				high = high.prev
		return temp


from typing import Optional
from typing import List

class Solution(object):

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		result = []
		if not head:
			return result
		tail = head
		while tail.next:
			tail = tail.next
		while head and tail and (head.data < tail.data):
			(headVal, tailVal) = (head.data, tail.data)
			currVal = headVal + tailVal
			if currVal == target:
				result.append((headVal, tailVal))
				head = head.next
				tail = tail.prev
			elif currVal > target:
				tail = tail.prev
			else:
				head = head.next
		return result


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		temp = head
		while temp:
			last = temp
			temp = temp.next
		ans = []
		start = head
		while start.data < last.data:
			if start.data + last.data == target:
				ans.append([start.data, last.data])
				start = start.next
				last = last.prev
			elif start.data + last.data > target:
				last = last.prev
			else:
				start = start.next
		return ans


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		first = head
		while first.next:
			first = first.next
		last = first
		first = head
		solution = []
		while first != last:
			if first.data + last.data == target:
				solution.append((first.data, last.data))
				if first.next == last:
					break
				first = first.next
				last = last.prev
			elif first.data + last.data > target:
				last = last.prev
			else:
				first = first.next
		return solution


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		(p1, p2) = (head, head)
		res = []
		while p2.next:
			p2 = p2.next
		while p1 and p2 and (p1.data < p2.data):
			t = p1.data + p2.data
			if t < target:
				p1 = p1.next
			elif t > target:
				p2 = p2.prev
			else:
				res.append([p1.data, p2.data])
				p1 = p1.next
				p2 = p2.prev
		return res


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		ans = []
		temp1 = temp2 = head
		while temp2.next:
			temp2 = temp2.next
		while temp2.data > temp1.data:
			sum = temp2.data + temp1.data
			if sum == target:
				ans.append([temp1.data, temp2.data])
				temp1 = temp1.next
				temp2 = temp2.prev
			elif sum < target:
				temp1 = temp1.next
			else:
				temp2 = temp2.prev
		return ans


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		if target is None:
			return []
		high = head
		while high.next is not None:
			high = high.next
		low = head
		res = []
		while id(low) != id(high):
			sumval = low.data + high.data
			if sumval == target:
				res.append([low.data, high.data])
				if id(low.next) != id(high):
					low = low.next
				high = high.prev
			elif sumval < target:
				low = low.next
			else:
				high = high.prev
		return res


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		end = head
		res = []
		while end.next is not None:
			end = end.next
		start = head
		while start != end:
			if start.data + end.data == target:
				res.append((start.data, end.data))
				start = start.next
				if start == end:
					break
				end = end.prev
			elif start.data + end.data > target:
				end = end.prev
			else:
				start = start.next
		return res


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		left = head
		right = head
		l = []
		while right.next != None:
			right = right.next
		while right != left and right.next != left:
			if left.data + right.data == target:
				l.append((left.data, right.data))
				left = left.next
				right = right.prev
			elif left.data + right.data < target:
				left = left.next
			else:
				right = right.prev
		return l


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		d = {}
		while head:
			d[head.data] = 1
			head = head.next
		a = []
		for i in d:
			if target - i in d and d[target - i] != -1 and (i != target - i):
				a.append(sorted([i, target - i]))
				d[i] = -1
		return sorted(a)


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		if not head.next:
			return []
		res = []
		low = high = head
		while high.next:
			high = high.next
		while low != high:
			if low.data + high.data == target:
				res.append([low.data, high.data])
				low = low.next
				if low == high:
					break
				high = high.prev
			elif low.data + high.data < target:
				low = low.next
			else:
				high = high.prev
		return res


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		tail = head
		while tail.next != None:
			tail = tail.next
		arr = []
		while head.data < tail.data:
			if head.data + tail.data == target:
				arr.append([head.data, tail.data])
				head = head.next
				tail = tail.prev
			elif head.data + tail.data > target:
				tail = tail.prev
			elif head.data + tail.data < target:
				head = head.next
		return arr


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		(fp, lp) = (head, head)
		while lp.next:
			lp = lp.next
		ans = []
		while fp and fp != lp:
			if fp.data + lp.data == target:
				ans.append([fp.data, lp.data])
				fp = fp.next
			elif fp.data + lp.data > target:
				lp = lp.prev
			else:
				fp = fp.next
		return ans


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		tail = head
		start = 1
		end = 1
		while tail.next != None:
			tail = tail.next
			end += 1
		sum = 0
		pairs = []
		while start < end:
			sum = head.data + tail.data
			if sum == target:
				pairs.append([head.data, tail.data])
				sum = 0
				head = head.next
				tail = tail.prev
				start += 1
				end -= 1
			elif sum > target:
				tail = tail.prev
				end -= 1
			else:
				head = head.next
				start += 1
		return pairs


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		(left, right) = (head, head)
		result = []
		while right.next:
			right = right.next
		while left != right:
			temp = left.data + right.data
			if temp == target:
				result.append([left.data, right.data])
				right = right.prev
			elif temp > target:
				right = right.prev
			elif temp < target:
				left = left.next
		return result


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		temp = head
		while temp:
			rear = temp
			temp = temp.next
		res = []
		while head and rear and (head.data < rear.data):
			x = head.data + rear.data
			if x == target:
				res.append((head.data, rear.data))
				head = head.next
				rear = rear.prev
			elif x < target:
				head = head.next
			else:
				rear = rear.prev
		return res


from typing import Optional
from typing import List

class Solution:

	def findPairsWithGivenSum(self, target: int, head: Optional['Node']) -> List[List[int]]:
		arr = []
		cur = head
		while cur.next is not None:
			cur = cur.next
		l = head
		r = cur
		while l != r and l.next != r:
			ld = l.data
			rd = r.data
			if ld + rd == target:
				arr.append((ld, rd))
				l = l.next
				r = r.prev
			elif ld + rd < target:
				l = l.next
			else:
				r = r.prev
		if l != r and l.data + r.data == target:
			arr.append((l.data, r.data))
		return arr