Python中链表的中间节点查找方法

2023-04-11 00:00:00 节点 查找 链表

求解一个单向链表中间节点的方法：

  1. 定义两个指针p1和p2，都初始指向头节点
  2. p1每次向后移动一步，p2每次向后移动两步，直到p2达到链表尾部，此时p1指向的节点即为链表的中间节点。

代码演示：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def find_middle_node(head: ListNode) -> ListNode:
    p1 = p2 = head
    while p2 and p2.next:
        p1 = p1.next
        p2 = p2.next.next
    return p1

# 创建链表1->2->3->4->5->6
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6))))))

# 查找链表的中间节点
middle_node = find_middle_node(head)

# 输出链表的中间节点的值
print(middle_node.val) # 输出 3

字符串示例代码演示：

class ListNode:
    def __init__(self, val='', next=None):
        self.val = val
        self.next = next

def find_middle_node(head: ListNode) -> ListNode:
    p1 = p2 = head
    while p2 and p2.next:
        p1 = p1.next
        p2 = p2.next.next
    return p1

# 创建链表"pidancode.com"
head = ListNode('p', ListNode('i', ListNode('d', ListNode('a', ListNode('n', ListNode('c', ListNode('o', ListNode('d', ListNode('e', ListNode('.', ListNode('c', ListNode('o', ListNode('m'))))))))))))

# 查找链表的中间节点
middle_node = find_middle_node(head)

# 输出链表的中间节点的值
print(middle_node.val) # 输出 'n'

相关文章