设计一个算法，将链表中所有节点的链接方向“原地”逆转，即要求仅利用原表的存储空间。即要求算法的空间复杂度为O(1)。

### 回答1：
算法思路：

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

2. 遍历链表，将当前节点的next指向前一个节点pre。

3. 更新pre、cur、next指针，将它们均向前移动一个节点。

4. 当cur指向最后一个节点时，将头节点指向cur（即原链表的最后一个节点），完成链表反转。

算法实现：

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

测试用例：

为了验证算法是否正确，我们需要设计一些测试用例。

1. 功能测试（链表中有多个节点）：

例如输入：1->2->3->4->5，预期输出：5->4->3->2->1。

2. 特殊输入测试（链表中只有一个节点或链表为nullptr）：

例如输入：1，预期输出：1。

例如输入：nullptr，预期输出：nullptr。

### 回答2：
要实现链表中所有节点链接方向的“原地”逆转，可以使用三个指针来完成。具体算法如下：

1. 初始化三个指针：prev指向空，curr指向链表的头节点，next指向curr的下一个节点。

2. 进行迭代，直到curr指向链表的尾节点为止：
- 将next指向的节点指向curr的前一个节点：next = curr.next
- 将curr的next指向prev节点：curr.next = prev
- 将prev指向curr节点：prev = curr
- 将curr指向next节点：curr = next

3. 遍历结束后，链表中所有节点的链接方向就已经被“原地”逆转了。此时，将链表的头节点设置为prev节点。

最后，需要注意的是，由于只使用了三个指针来进行节点的链接方向逆转，使用的额外空间为O(1)，因此算法的空间复杂度为O(1)。

以下是该算法的示例代码：

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

def reverseList(head):
    prev = None
    curr = head

    while curr is not None:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

    head = prev
    return head

可以通过以下方式调用该函数来测试算法的正确性：

# 创建一个链表：1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# 输出原始链表
print("Original List:")
curr = head
while curr is not None:
    print(curr.val, end=" -> ")
    curr = curr.next
print("None")

# 将链表的链接方向逆转
head = reverseList(head)

# 输出逆转后的链表
print("Reversed List:")
curr = head
while curr is not None:
    print(curr.val, end=" -> ")
    curr = curr.next
print("None")

输出结果为：

Original List:
1 -> 2 -> 3 -> 4 -> 5 -> None
Reversed List:
5 -> 4 -> 3 -> 2 -> 1 -> None

可以看到，逆转后的链表的链接方向已经被成功地原地逆转。

### 回答3：
这个问题可以使用迭代的方式来解决。我们可以设定三个指针来进行操作，分别为previous（记录前一个节点）、current（记录当前节点）和next（记录下一个节点）。

首先，我们将previous指向null节点，current指向链表的头部节点。然后，我们开始迭代，直到current指向null节点为止。在每一次迭代中，我们需要先将next指针指向current的下一个节点，以免丢失后续节点信息。然后，我们将current的next指针指向previous，将节点的链接方向进行逆转。接着，我们将previous指向current，current指向next。最后，继续下一次迭代直到处理完整个链表。

重复上述步骤，直到current指向null节点为止。最后，我们只需要将原本的链表头节点指向逆转后的最后一个节点即可。

该算法的时间复杂度为O(n)，其中n是链表的节点个数。空间复杂度为O(1)，因为我们只使用了常量级别的额外空间。

下面是算法的具体实现：

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class ReverseLinkedList {
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

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

        return previous;
    }
}

在这个算法中，我们从头开始迭代整个链表，逆转每个节点的指针方向。最终，我们返回逆转后的链表的头指针。