编写算法实现带头结点单链表的就地逆置，即利用原带头节点单链表的节点空间把元素序列 a0,a1…, an-1 逆置为an-1,…,a1,a0。

思路：

- 首先判断链表是否为空，或者链表只有一个节点，则不需要逆置。
- 定义三个指针：prev、cur和next，分别指向当前节点的前一个节点、当前节点和当前节点的下一个节点。
- 在遍历链表的过程中，依次将当前节点的 next 指针指向 prev，然后依次向后移动 prev、cur 和 next 指针。
- 遍历完成后，将原头结点的 next 指针指向新的表头节点。

代码实现：

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
    prev, cur, next = None, head.next, head.next.next
    while next:
        cur.next = prev
        prev, cur, next = cur, next, next.next
    cur.next = prev
    head.next = cur
    return head

其中，head 为带头结点的单链表头结点，返回值为逆置后的头结点。

相关问题

P39 编写算法实现带头结点单链表的就地逆置，即利用原带头节点单链表的节点空间把元素序列 a0,a1…, an-1 逆置为an-1,…,a1,a0。

算法实现如下：

1. 定义三个指针：pre、cur、suc，分别指向当前节点的前驱、当前节点、当前节点的后继。
2. 将 cur 指向头结点的下一个节点，pre 指向头结点，suc 指向 cur 的后继。
3. 遍历链表，对于每个节点，将其指向其前驱节点，然后依次更新 pre、cur、suc 指针。
4. 遍历结束后，将头结点的下一个节点指向 pre，完成链表的就地逆置。

代码实现如下：

void reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    ListNode* pre = head;
    ListNode* cur = head->next;
    ListNode* suc = cur->next;
    pre->next = nullptr;
    while (cur != nullptr) {
        cur->next = pre;
        pre = cur;
        cur = suc;
        if (suc != nullptr) {
            suc = suc->next;
        }
    }
    head->next = pre;
}

编写算法实现带头结点单链表的就地逆置，即利用原带头结点单链表的结点空间把元素序列a0,a1,…,an-1逆置为an-1,…,a1,a0。

要实现带头结点单链表的就地逆置，我们可以遵循以下步骤：

1. 初始化三个指针，分别为`prev`、`current`和`next`。其中`prev`指向当前节点的前一个节点，`current`指向当前节点，`next`指向当前节点的下一个节点。初始时，`prev`设置为头结点，`current`设置为头结点的下一个节点（即原链表的第一个元素节点）。

2. 遍历链表，对于每一个节点，先将`next`指针指向`current`节点的下一个节点，以保留后面节点的连接关系。

3. 然后将`current`节点的`next`指针指向前一个节点`prev`，从而实现当前节点的逆转。

4. 接着将`prev`和`current`指针都向前移动一个节点，即`prev`指向`current`，`current`指向`next`。

5. 重复上述步骤，直到`current`指针到达链表尾部（即`current`为`null`时），此时`prev`指针就指向了新的链表头。

6. 最后，将原链表的头结点的`next`指针指向`prev`，完成链表的逆转。

下面是使用伪代码表示的逆置过程：

function reverseLinkedList(head):
    if head is null or head.next is null:
        return head

    prev = head
    current = head.next
    next = null

    while current is not null:
        next = current.next
        current.next = prev
        prev = current
        current = next

    head.next = prev
    return head