用时间复杂度为n的算法，将一个长度为n的单链表逆序排列

可以使用迭代的方式对单链表进行逆序排列。具体步骤如下：

1. 定义三个指针，分别指向当前节点、前一个节点和后一个节点。
2. 将当前节点的 next 指针指向前一个节点。
3. 将前一个节点指针后移，指向当前节点。
4. 将当前节点指针后移，指向后一个节点。
5. 重复步骤2到4，直到当前节点为 null，表示已经遍历完整个链表。
6. 将链表的头节点指向前一个节点。

代码实现如下：

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;
}

时间复杂度为 O(n)，空间复杂度为 O(1)。

相关问题

用时间复杂度为n的算法，将一个长度为n的单链表逆序排列。

可以使用迭代法或递归法来实现单链表的逆序排列。

迭代法的实现思路是，依次将每个节点的 next 指针指向它的前驱节点。具体步骤如下：

1. 定义三个指针 prev、curr 和 next，分别指向当前节点的前驱节点、当前节点和当前节点的后继节点。
2. 遍历单链表，对于当前节点，将它的 next 指针指向它的前驱节点 prev，然后将 prev、curr 和 next 指针同时向右移动一个节点。
3. 当遍历到最后一个节点时，将它的 next 指针指向它的前驱节点 prev，并将它设为新的头节点。

代码如下：

def reverseList(head):
    if not head or not head.next:
        return head
    prev, curr, next = None, head, head.next
    while curr:
        curr.next = prev
        prev = curr
        curr = next
        next = next.next if next else None
    return prev

递归法的实现思路是，先递归地反转后续节点，然后将当前节点的 next 指针指向它的后继节点的后继节点。具体步骤如下：

1. 递归地反转当前节点后面的节点。
2. 将当前节点的 next 指针指向它的后继节点的后继节点。
3. 返回新的头节点。

代码如下：

def reverseList(head):
    if not head or not head.next:
        return head
    newHead = reverseList(head.next)
    head.next.next = head
    head.next = None
    return newHead

这两种方法的时间复杂度均为 O(n)，空间复杂度为 O(1)。

设计一个算法，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。

可以使用递归的方式实现单链表的逆序排列。具体实现如下：

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

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_head

这个算法的时间复杂度是 O(n)，空间复杂度是 O(n)，其中 n 是单链表的长度。