设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。

### 回答1：
算法如下：

1. 定义三个指针：pre、cur、next，分别指向前一个结点、当前结点和下一个结点。

2. 将cur指针指向链表的头结点。

3. 遍历链表，每次将cur指针指向的结点的next指针指向pre指针指向的结点，然后将pre、cur、next指针向后移动一个结点。

4. 当cur指针指向链表的尾结点时，遍历结束。

5. 将链表的头结点指向原链表的尾结点，即完成链表的逆转。

代码实现如下：

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

### 回答2：
算法如下：

1. 当链表为空或仅有一个节点时，直接返回原链表。

2. 从链表的第二个节点开始循环遍历，依次将每个节点的下一个节点指向它的前一个节点，直到遍历到最后一个节点。

3. 遍历完成后，将原链表的头节点指向原链表的尾节点。

代码如下：

Node* reverseList(Node* head) {
    if(head == NULL || head->next == NULL) { //链表为空或仅有一个节点时
        return head;
    }
    Node* pre = head; //指向前一个节点
    Node* cur = head->next; //指向当前节点
    Node* nxt = cur->next; //指向后一个节点
    while(cur != NULL) { //循环遍历链表
        cur->next = pre; //将当前节点的下一个节点指向前一个节点
        pre = cur; //将pre指向当前节点
        cur = nxt; //将cur指向后一个节点
        if(nxt != NULL) { //nxt指向后一个节点
            nxt = nxt->next; 
        }
    }
    head->next = NULL; //将原头节点与新的尾节点断开链接
    head = pre; //将头节点指向新的尾节点
    return head;
}

该算法的时间复杂度为O(n)，空间复杂度为O(1)。由于只利用原链表的存储空间，所以不会浪费额外的空间。

### 回答3：
算法分析：

单向链表的逆转是常见的面试考题，以下是一种实现方式：

首先我们定义三个指针：

- 前驱指针pre，初始为NULL
- 当前指针curr，初始为head
- 后继指针next，初始为curr->next

然后我们进行链表遍历，每次迭代中将curr的next指针指向它的前驱节点。然后将pre、curr、next三个指针向后移动一位，继续遍历。直到curr为NULL，此时链表的已经逆序。

算法实现：

下面是使用C++实现该算法的代码。其中，结构体Node代表单向链表的节点：

struct Node {
    int val;
    Node *next;
    Node(int val) : val(val), next(NULL) {}
};

然后定义一个函数reverse，接受一个头结点head，返回一个逆序后的新的头结点new_head：

Node* reverse(Node* head) {
    Node* pre = NULL;
    Node* curr = head;
    Node* next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

算法时间复杂度分析：

循环遍历了一次链表，算法的时间复杂度O(n)，空间复杂度O(1)。

算法优化：

可以改为递归实现：

Node* reverse(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node* new_head = reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return new_head;
}

参考：https://blog.csdn.net/qq_31120529/article/details/104464716