Python에서 단일 연결 목록의 중간 노드를 찾는 프로그램

<시간/>

단일 연결 목록 노드가 있다고 가정하고 중간 노드의 값을 찾아야 합니다. 그리고 두 개의 중간 노드가 있으면 두 번째 노드를 반환합니다. 이 문제를 단일 패스로 해결해야 합니다.

따라서 입력이 [5,9,6,4,8,2,1,4,5,2]와 같으면 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

p:=노드
d:=0, l:=0
노드가 null이 아닌 동안 수행
- d가 2와 같지 않으면
  - node:=노드의 다음
  - l :=l + 1, d :=d + 1
- 그렇지 않으면
p:=p의 다음, d:=0
- l이 홀수이면 p의 val을 반환하고 그렇지 않으면 p의 다음 값

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

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]