有头结点的单链表定位到尾结点的前驱成功的语句序列

假设头结点为`head`，则定位到尾结点的前驱可以使用如下语句序列：

node = head
while node.next.next is not None:
    node = node.next
prev = node

其中，`node`是当前节点，一开始指向头结点，然后每次将`node`指向它的下一个节点，直到`node.next.next`为`None`，即`node`指向倒数第二个节点。最后，将`prev`指向`node`，即为尾结点的前驱。

相关问题

对于有头结点的单链表写出定位到第i个结点的前驱ai-1的语句序列

在C++中，如果有一个指向单链表头节点的指针`head`，并且知道链表中的某个元素（例如第`i`个节点）的位置`i`，我们可以使用迭代的方式来找到第`i-1`个节点，也就是前驱节点。假设链表节点的结构为：

struct ListNode {
    int data;
    ListNode* next;
};

以下是一段示例代码，用于定位到第`i`个节点的前驱节点：

ListNode* findPredecessor(ListNode* head, int i) {
    if (i <= 0 || !head) return nullptr; // 如果索引不合法或链表为空，返回nullptr

    ListNode* current = head;
    for (int j = 1; j < i; ++j) {
        if (!current->next) return nullptr; // 避免越界
        current = current->next;
    }

    return current->prev; // 前一个节点就是我们要找的predecessor，如果没有prev，说明这是第一个节点
}

这里我们假设每个节点都有一个`prev`指针，用于引用它的前一个节点。如果没有这样的指针，我们需要在循环中每次移动`current`时同时检查下一个节点，直到找到位置`i`。

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