Python单链表中间节点查找程序

假设我们有一个单链表节点，我们需要找到中间节点的值。如果存在两个中间节点，则返回第二个节点的值。我们需要尝试在单次遍历中解决这个问题。

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

为了解决这个问题，我们将遵循以下步骤：

  • p := 节点

  • d := 0, l := 0

  • 当节点不为空时，执行以下操作：

    • 如果d不等于2，则

      • 节点 := 节点的下一个节点

      • 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))

输入

Input:
[5,9,6,4,8,2,1,4,5,2]

输出

2

更新于：2020年10月5日

浏览量：255

开启你的职业生涯

完成课程获得认证

开始学习
广告