मान लीजिए हमारे पास एक सिंगली लिंक्ड लिस्ट नोड है, हमें मध्य नोड का मान ढूंढना है। और जब दो मध्य नोड होते हैं, तो हम दूसरा वाला वापस करेंगे। हमें इसे सिंगल पास में हल करने का प्रयास करना है।
उदाहरण के लिए, यदि इनपुट [5,9,6,4,8,2,1,4,5,2] है, तो आउटपुट 2 होगा।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- p := node
- d := 0, l := 0
- जब तक node null नहीं है, करें:
- यदि d != 2, तो node := node.next, l := l+1, d := d+1
- अन्यथा, p := p.next, d := 0
- यदि l विषम है तो p.val वापस करें अन्यथा p.next.val
उदाहरण
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
class Solution:
def solve(self, node):
p = node
d = 0
l = 0
while node:
if d != 2:
node = node.next
l += 1
d += 1
else:
p = p.next
d = 0
return p.val if l & 1 else p.next.val
ob = Solution()
head = make_list([5,9,6,4,8,2,1,4,5,2])
print(ob.solve(head))
इनपुट
Input: [5,9,6,4,8,2,1,4,5,2]
आउटपुट
2