用 Python 编写程序来查找单链表的中间节点

pythonserver side programmingprogramming更新于 2026/1/9 4:28:17

假设我们有一个单链表节点，我们必须找到中间节点的值。当有两个中间节点时，我们将返回第二个节点。我们必须尝试一次性解决该问题。

因此，如果输入为 [5,9,6,4,8,2,1,4,5,2]，则输出为 2。

要解决该问题，我们将遵循以下步骤−

p:= node
d:= 0, l:= 0
当 node 不为空时，执行
- 如果 d 不等于 2，则
  - node:= next of node
  - l := l + 1, d := d + 1
- 否则，
p:= p 的下一个，d:= 0
- 当 l 为奇数时返回 p 的值，否则返回 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))