在一个带头结点的单链表中，头指针为L,如何把倒数第二个结点，插入到头结点的后面第一个工作结点的前面，写出关键伪代码。

1. 定义指针p和q，分别指向倒数第二个结点和头结点的后一个结点。
2. 遍历链表，使p指向倒数第二个结点，q指向头结点的后一个结点。
3. 将p指向的结点从链表中删除，并将其插入到q指向的结点的前面。
4. 修改头结点的指针，使其指向插入的结点。

伪代码如下：

p = L->next;
q = L->next->next;
while(q->next != NULL){
p = p->next;
q = q->next;
}
p->next = p->next->next;
p->next->next = L->next;
L->next = p->next;

相关问题

实现线性表的链式存储定义，完成单链表的创建（头插法、尾插法）、插入、删除、查找等常用操作，将线性链表逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，以此类推。

线性表的链式存储定义可以通过结构体和指针实现，如下所示：

typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node, *LinkedList;    // 定义Node为结构体类型，LinkedList为指向Node的指针类型

接下来我们可以实现单链表的创建、插入、删除和查找等常用操作。

### 头插法创建单链表

头插法是指将新节点插入到链表的头部，即新节点成为链表的第一个节点。以下是头插法创建单链表的代码实现：

LinkedList createListByHeadInsert(int* arr, int n) {
    LinkedList head = (LinkedList)malloc(sizeof(Node));  // 创建头节点
    head->next = NULL;  // 初始时链表为空
    for (int i = 0; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));  // 创建新节点
        newNode->data = arr[i];  // 赋值
        newNode->next = head->next;  // 插入到头节点后面
        head->next = newNode;
    }
    return head;
}

### 尾插法创建单链表

尾插法是指将新节点插入到链表的尾部，即新节点成为链表的最后一个节点。以下是尾插法创建单链表的代码实现：

LinkedList createListByTailInsert(int* arr, int n) {
    LinkedList head = (LinkedList)malloc(sizeof(Node));  // 创建头节点
    head->next = NULL;  // 初始时链表为空
    LinkedList tail = head;  // tail指向链表的最后一个节点
    for (int i = 0; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));  // 创建新节点
        newNode->data = arr[i];  // 赋值
        newNode->next = NULL;  // 新节点插入到尾部，所以指针域为NULL
        tail->next = newNode;  // 插入到链表尾部
        tail = newNode;  // 更新tail指针
    }
    return head;
}

### 插入节点

插入节点操作是将新节点插入到链表的任意位置。以下是插入节点的代码实现：

void insertNode(LinkedList list, int index, int data) {
    int i = 0;
    Node* p = list;
    while (p != NULL && i < index - 1) {  // 找到要插入的位置
        p = p->next;
        i++;
    }
    if (p == NULL || i > index - 1) {  // 如果超出链表长度，则直接返回
        return;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));  // 创建新节点
    newNode->data = data;  // 赋值
    newNode->next = p->next;  // 插入到p节点后面
    p->next = newNode;
}

### 删除节点

删除节点操作是将链表中的某个节点删除。以下是删除节点的代码实现：

void deleteNode(LinkedList list, int index) {
    int i = 0;
    Node* p = list;
    while (p != NULL && i < index - 1) {  // 找到要删除的位置
        p = p->next;
        i++;
    }
    if (p == NULL || p->next == NULL || i > index - 1) {  // 如果超出链表长度，则直接返回
        return;
    }
    Node* q = p->next;  // q指向要删除的节点
    p->next = q->next;  // 将q节点从链表中删除
    free(q);  // 释放q节点的内存
}

### 查找节点

查找节点操作是根据节点的值或者下标查找链表中的某个节点。以下是查找节点的代码实现：

Node* findNodeByValue(LinkedList list, int data) {
    Node* p = list->next;  // p指向第一个节点
    while (p != NULL && p->data != data) {  // 查找值为data的节点
        p = p->next;
    }
    return p;
}

Node* findNodeByIndex(LinkedList list, int index) {
    int i = 0;
    Node* p = list->next;  // p指向第一个节点
    while (p != NULL && i < index) {  // 查找下标为index的节点
        p = p->next;
        i++;
    }
    return p;
}

### 逆置链表

将链表逆置是指将链表中的所有节点按照相反的顺序重新排列。以下是逆置链表的代码实现：

LinkedList reverseList(LinkedList list) {
    if (list == NULL || list->next == NULL) {  // 如果链表为空或者只有一个节点，则直接返回
        return list;
    }
    Node* p = list->next;  // p指向第一个节点
    Node* q = p->next;  // q指向p的下一个节点
    p->next = NULL;  // 将第一个节点的指针域设为NULL
    while (q != NULL) {  // 逐个逆置节点
        Node* r = q->next;  // r指向q的下一个节点
        q->next = p;  // 将q的指针域指向p
        p = q;  // 更新p指针
        q = r;  // 更新q指针
    }
    list->next = p;  // 将头节点指向p节点
    return list;
}

以上就是线性表的链式存储定义以及单链表的创建、插入、删除、查找等常用操作的代码实现。

用C语言完成以下链表4个典型应用的解题思路和代码撰写 1、链表原地逆置 2、求链表的中间(中左)结点 3、求链表的倒数第k个结点 4、2个有序链表的

1. **链表原地逆置**: 这个问题通常通过三个指针（两个快慢指针和一个反转指针）来解决。首先让快指针每次走两步，慢指针每次走一步，当快指针到达链表尾部时，慢指针的位置就是原链表的中间位置。然后从慢指针开始到头节点，依次将节点指向它的后继节点，实现了原地逆置。

void reverseList(struct Node** head) {
    struct Node* prev = NULL;
    struct Node* current = *head;
    struct Node* next = NULL;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head = prev;
}

2. **求链表的中间结点**: 可以借助双指针，一个移动速度快一倍，当快慢指针相遇时，慢指针所指的就是链表的中间结点。

struct Node* findMiddleNode(struct Node* head) {
    if (head == NULL || head->next == NULL)
        return head;
    struct Node* slow = head;
    struct Node* fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

3. **求链表的倒数第k个结点**: 这需要先找到链表的长度，然后从头节点开始向前移动k次。如果链表长度小于k，则返回NULL。

struct Node* kthFromEnd(struct Node* head, int k) {
    int length = countNodes(head);
    if (length < k)
        return NULL;
    Node* temp = head;
    for (int i = 0; i < length - k; i++)
        temp = temp->next;
    return temp;
}

int countNodes(struct Node* node) {
    if (node == NULL)
        return 0;
    return 1 + countNodes(node->next);
}

4. **2个有序链表合并**: 遇到相同值的情况下，可以优先选择第一个链表的节点。两个指针分别遍历两个链表，直到其中一个链表遍历完。

struct Node* mergeTwoLists(struct Node* l1, struct Node* l2) {
    struct Node* result = NULL, *temp = NULL;
    if (l1 == NULL)
        return l2;
    else if (l2 == NULL)
        return l1;
    
    if (l1->val <= l2->val) {
        result = l1;
        result->next = mergeTwoLists(l1->next, l2);
    } else {
        result = l2;
        result->next = mergeTwoLists(l1, l2->next);
    }
    
    return result;
}