已知一个带头节点的单链表，结点结构为（data,next）,假设该链表只给出了头指针l，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置的结点（k为正整数）。若查找成功，算法

如下：

1. 定义两个指针p和q，初始时均指向头节点l。
2. 让指针p先走k步，此时指针q和指针p之间的距离为k。
3. 然后同时移动指针p和指针q，每次移动一步，直到指针p到达链表末尾。
4. 此时指针q所指向的节点即为倒数第k个节点。

算法的时间复杂度为O(n)，其中n为链表的长度。

相关问题

已知头指针h指向一个带头节点的非空单循环链表，节点结构为data，next，其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现在要删除该链表的第一个元素，语句是什么

要删除单循环链表的第一个元素，需要先找到尾节点，然后将尾节点的next指针指向第二个节点，再释放头节点的内存空间。具体的语句如下：

q = h->next;  // 将临时指针q指向第一个节点
p->next = q->next;  // 将尾指针p的next指针指向第二个节点
h->next = q->next;  // 将头节点h的next指针指向第二个节点
free(q);  // 释放第一个节点的内存空间

写一个函数，完成如下功能：已知指针la、lb分别指向一个带头结点的非递减有序单链表，将其合并成一个带头结点的非递减有序单链表。

### 回答1：

void mergeList(ListNode* la, ListNode* lb) {
    ListNode* pa = la->next;
    ListNode* pb = lb->next;
    ListNode* pc = la;
    while (pa && pb) {
        if (pa->val <= pb->val) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    delete lb; // 释放lb的头结点空间
}

思路：设置三个指针pa、pb、pc，分别指向la、lb、合并后的链表的最后一个节点。然后，依次比较pa和pb所指向的节点的值的大小，将小的节点接到pc的后面，同时移动指针。最后，将剩余的节点接到pc的后面。最后，释放lb的头结点空间。

### 回答2：
可以使用迭代法来合并两个有序链表。具体步骤如下：

1. 定义一个新的链表lc，并初始化为一个带头结点的空链表，令指针lc指向头结点。

2. 定义两个指针pa和pb，分别指向链表la和lb的头结点，并将pa和pb分别初始化为la和lb的第一个结点。

3. 遍历链表la和lb，直到pa和pb都指向链表的尾结点。

4. 比较pa和pb指向的结点的值，将较小的值插入到链表lc中，并更新指针pa或pb，插入一个新的结点。

5. 如果链表la或lb遍历完后，仍有结点未插入到链表lc中，则将剩余的结点插入到lc中。

6. 返回合并后的链表lc。

以下是一个示例代码实现：

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

struct ListNode *mergeList(struct ListNode *la, struct ListNode *lb) {
    // 初始化合并后的链表lc
    struct ListNode *lc = (ListNode *)malloc(sizeof(ListNode));
    lc->next = NULL;
    struct ListNode *pc = lc;

    // 初始化指针pa和pb
    struct ListNode *pa = la->next;
    struct ListNode *pb = lb->next;

    // 循环遍历la和lb
    while (pa && pb) {
        // 比较两个指针指向的结点值
        if (pa->val <= pb->val) {
            // 将较小的结点插入到lc中
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }

    // 将剩余的结点插入到lc中
    pc->next = pa ? pa : pb;

    return lc;
}

以上代码中，lc指向合并后的链表的头结点，利用两个指针pa和pb依次比较两个链表的结点值，并将较小的结点插入到lc中，最后将剩余的结点插入到lc中。返回合并后的链表lc。

### 回答3：
可以定义一个函数 mergeList，该函数接受两个带头结点的非递减有序单链表的头指针，将它们合并成一个带头结点的非递减有序单链表的头指针。

首先创建一个新的头结点，并将其指针指向 NULL，作为合并后链表的头结点。

初始化两个指针 p 和 q，分别指向两个链表的第一个元素，同时定义一个指针 r，指向新链表的当前操作节点。

在进行合并操作时，比较 p 和 q 指针所指节点的值的大小：

- 若 p 指针所指节点的值小于等于 q 指针所指节点的值，将当前节点的下一个指针指向 p，并将 p 指针指向下一个节点。
- 若 p 指针所指节点的值大于 q 指针所指节点的值，将当前节点的下一个指针指向 q，并将 q 指针指向下一个节点。

遍历完其中一个链表后，将剩余链表的剩余部分直接接到新链表的最后。

最后返回合并后链表的头结点即可。

函数的具体实现如下：

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

Node* mergeList(Node* la, Node* lb) {
    Node* lc = new Node(); // 创建新链表的头结点
    lc->next = NULL;
    
    Node* p = la->next; // 指向la的第一个元素
    Node* q = lb->next; // 指向lb的第一个元素
    Node* r = lc; // 指向新链表的当前操作节点
    
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            r->next = p;
            p = p->next;
        } else {
            r->next = q;
            q = q->next;
        }
        r = r->next;
    }
    
    // 处理剩余部分
    if (p != NULL) {
        r->next = p;
    }
    if (q != NULL) {
        r->next = q;
    }
    
    return lc;
}

调用该函数并打印结果：

int main() {
    // 创建链表la
    Node* la = new Node();
    la->next = new Node();
    la->next->data = 1;
    la->next->next = new Node();
    la->next->next->data = 3;
    la->next->next->next = new Node();
    la->next->next->next->data = 5;
    la->next->next->next->next = NULL;

    // 创建链表lb
    Node* lb = new Node();
    lb->next = new Node();
    lb->next->data = 2;
    lb->next->next = new Node();
    lb->next->next->data = 4;
    lb->next->next->next = new Node();
    lb->next->next->next->data = 6;
    lb->next->next->next->next = NULL;

    // 合并两个链表
    Node* lc = mergeList(la, lb);

    // 输出合并后链表的元素
    Node* cur = lc->next;
    while (cur != NULL) {
        cout << cur->data << " ";
        cur = cur->next;
    }
    
    return 0;
}

运行上述代码，输出结果为：1 2 3 4 5 6，表示合并后的有序链表的元素。