利用单链表原来的结点空间逆转一个单链表

可以使用三个指针，分别指向当前结点、前一个结点和后一个结点。遍历单链表，将当前结点的 next 指针指向前一个结点，然后将三个指针分别向后移动一个结点，直到遍历完整个单链表。最后将原来的头结点指向新的尾结点即可。

具体实现代码如下：

def reverse_list(head):
    if not head or not head.next:
        return head
    pre = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    return pre

其中，head 表示原来的头结点，pre 表示前一个结点，cur 表示当前结点，nxt 表示后一个结点。在遍历过程中，将当前结点的 next 指针指向前一个结点，然后将三个指针分别向后移动一个结点。最后返回新的头结点 pre。

相关问题

利用单链表原来的结点空间将一个单链表就地逆转

### 回答1：
可以使用三个指针prev, curr, next，分别指向前一个结点、当前结点和下一个结点。然后依次遍历链表，将当前结点的next指针指向前一个结点，然后将三个指针依次向后移动。最后将原链表的头结点指向原链表的尾结点即可。

以下是示例代码：

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

### 回答2：
要将一个单链表就地逆转，即需要利用单链表原来的结点空间进行操作。具体的步骤如下：

1. 初始化三个指针：pre指向当前结点的前一个结点，cur指向当前结点，next指向当前结点的下一个结点。初始时pre和next均为NULL，cur指向单链表的头结点。

2. 进入循环，循环条件为cur不为NULL。在循环中进行如下操作：
- 将cur的next指针指向pre，即将当前结点的指针方向反转。
- 更新pre、cur和next的指向，使它们分别指向当前结点、当前结点的下一个结点和当前结点的下一个结点的下一个结点。

3. 当循环结束时，pre指向原链表的最后一个结点，cur为NULL。此时需要再进行最后一步操作：
- 将原链表的头结点指向原链表的最后一个结点，即将原链表翻转。
- 将原链表的最后一个结点指向NULL，作为新链表的尾结点。

通过以上步骤，就能够将一个单链表就地逆转。这个操作的时间复杂度为O(n)，其中n为链表的长度。

### 回答3：
要将一个单链表就地逆转，即不使用额外的空间，可以按照以下步骤进行操作。

1. 初始化三个指针pre、curr和next。pre指向当前结点的前一个结点（初始为null），curr指向当前结点（初始为第一个结点），next指向当前结点的下一个结点（初始为null）。

2. 遍历整个链表，直到curr指向null为止。在每一次遍历中，执行以下操作：

a. 将next指向curr的下一个结点。

b. 把curr的下一个结点改为pre。

c. 把pre指向curr。

d. 把curr指向next。

3. 遍历完成后，链表已经逆转，此时pre指向原链表的最后一个结点，curr指向null。

4. 要使整个链表指向逆转后的第一个结点，可以定义一个新的指针head，将pre赋给head。

5. 返回head作为逆转后的链表的头指针。

这样，就能够利用单链表原来的结点空间将一个单链表就地逆转。

设计一个算法，利用单链表原来的结点空间逆转一个单链表

可以使用三个指针分别指向当前结点、前一个结点和后一个结点，然后依次遍历单链表，将当前结点的 next 指针指向前一个结点，然后将三个指针向后移动一个结点，直到遍历完整个单链表。最后将原来的头结点指向新的尾结点即可。

具体实现如下：

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

其中，head 是原来的头结点，prev 是前一个结点，curr 是当前结点，next 是后一个结点。在遍历过程中，首先将 next 指针指向当前结点的下一个结点，然后将当前结点的 next 指针指向前一个结点，最后将 prev 和 curr 向后移动一个结点。遍历完整个单链表后，将原来的头结点指向新的尾结点 prev 即可。