单链表中间节点

Author Avatar
Yangzzz 7月 27, 2020
283字 | 1分 |
  • 在其它设备中阅读本文章

单链表中间节点

方法一

首先先遍历一遍获得节点个数,然后取一半作计数器再次遍历。这个方法遍历了两次,是最慢的方法

class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next


n1 = Node("1", None)
n2 = Node("2", n1)
n3 = Node("3", n2)
n4 = Node("4", n3)
n5 = Node("5", n4)

head = n5  # 链表的头节点

index = 0  # 总节点数
while head.next is not None:
    index += 1
    head = head.next

head = n5
for i in range(0, int(index / 2)):
    head = head.next

print(head.data)

方法二

一个指针(P1)每次步进一个节点,另一个指针(P2)每次步进两个节点。当P2遍历到链表尾时,P1正好遍历到中间节点。(这个思路真的学到了)

class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next

n1 = Node("1", None)
n2 = Node("2", n1)
n3 = Node("3", n2)
n4 = Node("4", n3)
n5 = Node("5", n4)

head = n5  # 链表的头节点

P1 = head  # 一次步进1个node
P2 = head  # 一次步进2个node

while P2.next is not None and P2.next.next is not None:
    P2 = P2.next.next
    P1 = P1.next

print(P1.data)

本文使用CC BY-NC-SA 3.0 中国大陆协议许可
本文链接:https://myxy99.cn/posts/python/a85bf3bb.html