用java写一段代码，实现将单向链表进行逆序操作

下面是一段Java代码，实现将单向链表进行逆序操作：

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;  // 保存下一个节点
        curr.next = prev;  // 当前节点指向前一个节点
        prev = curr;  // 更新前一个节点
        curr = next;  // 更新当前节点
    }
    return prev;  // 返回新的头节点
}

这段代码中，我们使用了三个指针来对链表进行逆序操作。prev指针指向前一个节点，curr指针指向当前节点，next指针指向下一个节点。我们每次将当前节点的next指针指向前一个节点，然后更新prev和curr指针，直到遍历到链表的末尾。

最后，我们返回新的头节点prev，即为逆序后的链表的头节点。

需要注意的是，在实际应用中，可能需要在逆序操作完成后更新链表的头节点。

相关问题

java 数据结构实现

### 常见数据结构的Java实现

#### 数组
数组是一种基本的数据结构，在Java中可以通过声明一个特定类型的变量来创建。一旦定义，其大小不可改变。

int[] array = new int[10];

为了操作数组中的元素，可以直接通过索引来访问或修改它们[^1]。

#### 链表
链表由一系列节点组成，每个节点包含数据部分以及指向下一个节点的链接。对于双向链表而言，则还包含了指向前一节点的链接。下面是一个简单的单向链表示例：

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

要从尾到头打印链表，可以采用递归的方法或是利用栈这种后进先出(LIFO)特性来进行逆序处理[^3]。

#### 栈
栈也是一种线性的数据结构，遵循后进先出的原则。当新元素加入时称为压栈（push），而移除最上面的一个元素则被称为弹栈（pop）。这里给出基于固定长度数组构建的简单栈类的一部分代码片段:

public class ArrayStack {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elements;
    private int size = 0;

    public ArrayStack() {
        this.elements = new Object[DEFAULT_CAPACITY];
    }

    public boolean isFull(){
        return size >= elements.length;
    }

    public void push(Object item){
        if(isFull()){
            resize();
        }
        elements[size++] = item;
    }

    private void resize(){
        Object[] newArray = Arrays.copyOf(elements,elements.length*2);
        elements=newArray;
    }
    
    // ... pop and other methods ...
}

这段代码展示了如何安全地执行入栈操作，并且在必要时候自动调整内部存储空间以适应更多的项目[^4]。

#### 排序与比较器模式
有时候需要自定义对象之间的排序逻辑。这可以通过让某个类实现`Comparator<T>`接口并重写其中的compare方法完成。例如按照学生的年龄升序排列学生列表就可以这样来做：

Collections.sort(studentList, new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        return Integer.compare(o1.getAge(),o2.getAge());
    }
});

上述例子中，匿名内部类被用来提供具体的比较行为给通用工具函数使用[^2]。

java408单链表

### Java 408 单链表实现与常见问题

#### 链表节点个数计算
为了求取单链表中节点的数量，可以遍历整个链表并计数。每访问到一个新的节点，则增加计数值直到到达链表末端。

public int size() {
    Node current = head;
    int count = 0;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

此方法能够有效地统计链表长度[^1]。

#### 查找倒数第 k 个节点
要找到链表中的倒数第 `k` 个节点，可以通过双指针法来完成这一目标。先让第一个指针向前移动 `k` 步，随后两个指针同步前进直至前导指针抵达终点位置；此时跟随指针所指向的就是所需的结果节点。

public ListNode findKthFromEnd(int k) {
    if (head == null || k <= 0) {
        throw new IllegalArgumentException("Invalid input");
    }

    ListNode fast = head, slow = head;

    // Move the fast pointer ahead by 'k' steps.
    for (int i = 0; i < k && fast != null; ++i) {
        fast = fast.next;
    }

    // If there are less than 'k' nodes in list then it's an error case.
    if (fast == null && i < k) {
        throw new NoSuchElementException();
    }

    // Now move both pointers until we reach end of linkedlist.
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    return slow;
}

这种方法利用了两次迭代过程完成了任务，在时间复杂度上达到了 O(n)。

#### 反转单向链表
反转单链表意味着改变各节点之间的连接方向，使得原本的尾部成为新的头部。具体做法是从头至尾依次处理每个节点，并将其 next 字段重新设置为其前置节点。

public static ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while(curr != null){
        ListNode tempNext = curr.next;
        curr.next = prev;
        prev = curr;
        curr = tempNext;
    } 

    return prev;
}

这段代码展示了如何高效地执行链表翻转操作[^3]。

#### 逆序打印链表
如果想要按照相反顺序输出链表元素，可以选择递归方式或是借助栈这种先进后出的数据结构来进行辅助存储再逐项弹出来显示。

采用递归的方式：

private void printReverseRecursive(Node node) {
    if(node==null)
       return ;
    printReverseRecursive(node.next);
    System.out.print(node.data+" ");
}

上述函数会一直深入调用自己直到遇到终止条件（即当前节点为空），之后才开始真正意义上的打印工作。