已知head 指向一个带头结点的单向链表，链表中每个节点包含字符型数据和和指向本结构节点的指针，编写程序实现如下图所示的逆置

假设链表的头结点为head，可以按照以下步骤实现链表逆置：

1. 定义三个指针：p, q, r。其中p指向头结点，q指向第一个节点，r指向q的后继节点；
2. 将p的next指向空节点，表示新链表的结尾；
3. 依次遍历链表，对于每个节点，将q的next指向p，实现节点的逆置；
4. 将p、q、r依次向后移动一个节点，直到r指向空节点，表示遍历到了链表的尾部；
5. 将头结点的next指向q，表示新的头结点为原链表的尾节点；
6. 返回头结点head。

具体实现代码如下：

void reverseList(Node *head) {
    Node *p = head, *q = head->next, *r = q->next;
    p->next = NULL;
    while (r) {
        q->next = p;
        p = q;
        q = r;
        r = r->next;
    }
    q->next = p;
    head->next = q;
}

其中，Node为链表节点的结构体，包含数据和指向下一个节点的指针。

相关问题

已知head 指向一个带头结点的单向链表，链表中每个节点包含字符型数据long 和和指向本结构节点的指针，编写程序实现如下图所示的逆置

假设链表头结点为head，可以按照如下步骤逆置链表：

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

2. 将p指针指向头结点的下一个节点，pre指向头结点。

3. 循环遍历链表，每次将p指针所指节点的next指针指向pre节点，然后将pre、p、next三个指针向后移动一个节点，直到p指针指向NULL。

4. 最后将头结点的next指针指向pre节点，完成链表的逆置。

具体代码实现如下：

void reverseList(Node* head) {
    if (head == NULL || head->next == NULL) {
        return;  // 链表为空或者只有一个节点，无需逆置
    }
    Node *pre = head, *p = head->next, *next;  // 定义三个指针
    pre->next = NULL;  // 头结点的next指针置为NULL
    while (p != NULL) {
        next = p->next;  // 先保存p节点的下一个节点
        p->next = pre;   // 将p节点的next指针指向pre节点
        pre = p;         // pre、p、next三个指针向后移动一个节点
        p = next;
    }
    head->next = pre;   // 将头结点的next指针指向pre节点
}

已知head指向一个带头结点的单向链表，链表中每个结点包含字符串数据和指向本结构结点的指针。编写函数实现在值为“jone”的结点前插入值为输入值的结点，若没有值为“jone”的结点，则插在链表最后。

题目描述：已知head指向一个带头结点的单向链表，链表中每个结点包含字符串数据和指向本结构的指针。编写函数实现在值为“jone”的结点前插入值为输入值的结点，若没有值为“jone”的结点，则插入在链表最后。

解题思路：遍历链表，若遇到值为“jone”的结点则在其前面插入新结点，否则在链表最后插入新结点。

Python代码：