带头结点的单链表求前驱代码

以下是带头结点的单链表求前驱的代码实现：

// 带头结点的单链表结构体定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 求指定节点的前驱节点
ListNode* findPredecessor(ListNode* head, ListNode* target) {
    ListNode* p = head;
    while (p->next != NULL && p->next != target) {
        p = p->next;
    }
    if (p->next == target) {
        return p;
    } else {
        return NULL;
    }
}

上述代码中，`findPredecessor` 函数接受两个参数：一个是带头结点的单链表的头结点指针 `head`，另一个是指定节点的指针 `target`。函数的返回值是指定节点的前驱节点指针，如果指定节点没有前驱，则返回 `NULL`。

函数的实现思路是从头结点开始遍历链表，找到指定节点的前一个节点即可。遍历过程中需要注意边界条件的处理。

相关问题

将输入的带头结点单链表倒置代码

以下是将带头结点的单链表倒置的代码：

void reverseList(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return; // 链表为空或只有一个节点，直接返回
    }
    Node* prev = nullptr;
    Node* curr = head->next;
    while (curr != nullptr) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head->next = prev;
}

其中，`Node` 是单链表节点的结构体，包含一个 `int` 类型的数据成员 `data` 和一个指向下一个节点的指针 `next`。`head` 是指向链表头结点的指针，即 `head->next` 指向链表的第一个节点。在代码中，我们使用三个指针 `prev`、`curr` 和 `next`，分别表示当前节点的前驱、当前节点和当前节点的后继。在遍历链表的过程中，我们每次将当前节点的 `next` 指针指向它的前驱，然后将 `prev`、`curr`、`next` 分别向后移动一个节点，直到遍历完整个链表。最后，将头结点的 `next` 指针指向反转后的链表的第一个节点。

编写实现带头结点单链表就地逆置的成员函数

以下是C++代码实现：

void LinkedList::reverse() {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    Node* prev = nullptr;
    Node* current = head->next;
    Node* next = current->next;
    while (next != nullptr) {
        current->next = prev;
        prev = current;
        current = next;
        next = next->next;
    }
    current->next = prev;
    head->next = current;
}

该函数首先判断链表是否为空或仅有一个节点，如果是，则直接返回。否则，定义三个指针变量：`prev`、`current`和`next`。其中，`prev`指向前驱节点，`current`指向当前节点，`next`指向后继节点。初始时，`prev`为`nullptr`，`current`为头结点的下一个节点，`next`为`current`的下一个节点。然后，进入循环，将`current`的`next`指针指向`prev`，然后将三个指针变量向后移动一位。当`next`为`nullptr`时，循环结束。最后，将`current`的`next`指向`prev`，将头结点的`next`指针指向`current`，完成链表的逆置。