用Java实现在原链表上进行翻转

可以通过迭代和递归两种方法实现在原链表上进行翻转。

迭代方法：

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

递归方法：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

以上两种方法都可以实现在原链表上进行翻转，时间复杂度均为 O(n)，空间复杂度均为 O(1)。

相关问题

用Java写一个链表翻转

在 Java 中，你可以使用以下代码来实现链表翻转:

public class LinkedList {
    private Node head;

    private static class Node {
        private int data;
        private Node next;

        private Node(int data) {
            this.data = data;
        }
    }

    public void addToFront(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    public void reverse() {
        Node current = head;
        Node previous = null;
        Node next = null;

        while (current != null) {
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }

        head = previous;
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addToFront(1);
        list.addToFront(2);
        list.addToFront(3);
        list.addToFront(4);
        list.addToFront(5);

        System.out.println("Original list: ");
        list.printList();
        System.out.println();

        list.reverse();

        System.out.println("Reversed list: ");
        list.printList();
    }
}

这段代码实现了一个单向链表类，包含了一些基本的方法，比如添加节点、翻转链表、打印链表。

链表翻转的具体实现在 `reverse` 方法中，通过循环不断地将当前节点的 next 指针指向前一个节点，最后将头节点更新为原来的尾节点即可实现链表翻转。

运行上面的代码，你会得到如下输出:

Original list: 
5 4 3 2 1 
Reversed list: 
1 2 3 4 5 

这就是如何使用 Java 实现链表翻转的基本方法。希望