Java 第79题：单链表节点类：头插法建立并遍历

题目

定义单链表节点结构体，使用头插法（Head Insertion）依次读入 n 个整数建立单向链表，并顺序遍历输出链表中各节点的值。

输入格式：第一行输入节点数量 n；第二行输入 n 个整数。

输出格式：按链表当前从头到尾的顺序输出各节点数据，末尾换行。

数据范围与约定：1 ≤ n ≤ 100。

思路与算法

1. 链表节点内存动态分配
为每个新节点调用 new(sizeof(struct Node)) 申请堆内存。

2. 头插法指针重连
核心操作：node->next = head; head = node;。新节点始终插入在表头位置，因此最终遍历出来的顺序恰好是输入的逆序。

3. 内存释放习惯
程序结束前应顺着指针释放每个动态分配的节点，养成防止内存泄漏的规范。

完整程序

import java.util.Scanner;

class Node {
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = null;

        // 头插法构建单向链表
        for (int i = 0; i < n; i++) {
            int v = sc.nextInt();
            Node node = new Node(v);
            node.next = head;
            head = node;
        }

        // 顺序遍历链表节点
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + (cur.next != null ? " " : "\n"));
            cur = cur.next;
        }
    }
}

运行示例

输入：

3
1 2 3

输出：

3 2 1