6-2 LinkList2-单链表A拆分成奇数和偶数值单链表B和C【有题解视频，可本地编译器调试】 分数 10 作者 通信DS课程组 单位 成都信息工程大学 在一个带头结点的单链表A中，头指针为a，设计算法SplitList ( )将A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值为奇数的结点， 而C表的结点为A表中值为偶数的结点（链表A的元素类型为整型，要求B、C表除了头结点可以新开辟空间外，其余结点均利用A表的结点，不得申请新的结点空间）最后要求遍历B，C链表。

以下是实现SplitList()函数的C++代码：

void SplitList(LinkList &a, LinkList &b, LinkList &c) {
    // 初始化链表b和c
    InitList(b);
    InitList(c);
    LNode *p = a->next, *pb = b, *pc = c;
    while (p != NULL) {
        if (p->data % 2 == 1) { // 如果是奇数，插入到链表b中
            pb->next = p;
            pb = pb->next;
        } else { // 如果是偶数，插入到链表c中
            pc->next = p;
            pc = pc->next;
        }
        p = p->next;
    }
    pb->next = NULL; // 链表b的末尾置为NULL
    pc->next = NULL; // 链表c的末尾置为NULL
}

主要思路是遍历链表A，将奇数插入到链表B，偶数插入到链表C。在插入时，需要维护链表B和C的尾指针，以便于在最后将尾指针置为NULL。

相关问题

6-2 单链表基本运算算法的实现

单链表是一种常用的数据结构，它由若干个结点组成，每个结点包含一个数据域和一个指向下一个结点的指针。单链表的基本操作包括：初始化、插入结点、删除结点、查找结点等。下面是单链表基本运算算法的实现。

首先，定义单链表的结点结构体：

typedef struct LNode {
    DataType data;
    struct LNode *next;
} LNode, *LinkList;

其中，`DataType`为数据类型，可以根据实际需求进行定义。

初始化单链表：

void InitList(LinkList *L) {
    *L = (LinkList) malloc(sizeof(LNode));
    (*L)->next = NULL;
}

插入结点：

void InsertList(LinkList L, int pos, DataType x) {
    int index = 0;
    LinkList p = L, q;
    while (p && index < pos - 1) {
        p = p->next;
        index++;
    }
    if (!p || index > pos - 1) {
        printf("Invalid position.\n");
        return;
    }
    q = (LinkList) malloc(sizeof(LNode));
    q->data = x;
    q->next = p->next;
    p->next = q;
}

删除结点：

void DeleteList(LinkList L, int pos) {
    int index = 0;
    LinkList p = L, q;
    while (p->next && index < pos - 1) {
        p = p->next;
        index++;
    }
    if (!p->next || index > pos - 1) {
        printf("Invalid position.\n");
        return;
    }
    q = p->next;
    p->next = q->next;
    free(q);
}

查找结点：

LinkList FindList(LinkList L, DataType x) {
    LinkList p = L->next;
    while (p != NULL && p->data != x) {
        p = p->next;
    }
    return p;
}

需要注意的是，在插入和删除结点时，需要保证传入的位置参数`pos`合法，即在链表的范围之内。此外，当查找结点时，如果找到了指定的元素，则返回它所在的结点的指针；如果没有找到，则返回`NULL`。

完整代码如下：

linklist6-查询单链表倒数第k个链点的元素

### 回答1：
要实现单链表倒数第k个节点的元素，需要遍历整个链表，记录链表的长度，然后再从头开始遍历找到倒数第k个节点。可以使用两个指针，一个先走k步，然后另一个和它一起走，直到先走的那个指针走到链表尾部，此时后面的指针即为倒数第k个节点。

### 回答2：
单链表是一种比较常见的数据结构，在实际的编程中也经常会用到。而查询单链表倒数第k个链点的元素也是一道非常常见的面试题。

我们可以考虑利用双指针法来解决这个问题。具体步骤如下：

1.定义两个指针p和q，都指向单链表的头结点。

2.让指针p先移动k个位置，然后再让指针q开始从头结点开始逐个向后移动。

3.当指针p移动到链表的尾部时，此时q所指向的结点就是倒数第k个链点。

例如，我们有如下的一条单链表：1->2->3->4->5，如果要求查询倒数第2个链点的元素，那么我们可以按照上述方法进行操作：

1.让指针p先移动2个位置，指向的是数字3所在的结点。

2.此时让指针q开始逐个向后移动，当指针p到达链表尾部时，q所指向的结点就是倒数第2个链点，也就是数字4所在的结点。

3.最后返回数字4即可。

需要注意的是，在实际编程中，我们需要考虑一些特殊情况。例如，如果链表为空或者链表的长度小于k时，此时我们需要做出相应的异常处理。

总之，通过双指针法来查询单链表倒数第k个链点的元素，是一种简单、高效的解决方式。在实际的工作中，我们需要掌握这种基本的数据结构操作，并能够熟练运用。

### 回答3：
题目描述

给定一个单链表，请找出该链表倒数第k个链点的元素。

解题思路

遍历整个链表，记录链表长度len，然后再次从头遍历链表，当遍历到第len − k + 1个节点时，该节点就是我们要找的倒数第k个节点。

实现步骤

1. 定义两个指针pHead和pMove指向头结点，pMove向后移动k-1次。

2. 然后，同时移动pHead和pMove，直到pMove指向链表的末尾。

3. 移动后，pHead指向的就是倒数第k个节点。

需要注意的是：

1. k为0和链表为空时需要特殊处理。

2. 链表长度不足k的情况需要特殊处理。

3. 可以使用快慢指针来实现。

代码实现

C++实现

ListNode* FindKthToTail(ListNode* head, int k) {
if (head == nullptr || k == 0) return nullptr; //判断特殊情况
ListNode* slow = head;
ListNode* fast = head;
for (int i = 0; i < k - 1; ++i) {
if (fast->next != nullptr) {
fast = fast->next;
} else {
return nullptr; //链表长度不足k时返回nullptr
}
}
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
return slow; //返回倒数第k个节点
}

Python实现

class Solution:
def FindKthToTail(self, head: ListNode, k: int) -> ListNode:
if not head or k == 0:
return None # 判断特殊情况
slow, fast = head, head
for i in range(k - 1):
if fast.next:
fast = fast.next
else:
return None # 链表长度不足k时返回None
while fast.next:
fast, slow = fast.next, slow.next
return slow # 返回倒数第k个节点

时间复杂度

遍历链表两次，时间复杂度为O(n)。

空间复杂度

只需要定义两个指针，空间复杂度为O(1)。

总结

找到倒数第k个节点的元素是链表操作中比较常见的操作之一。使用这种方法可以遍历链表一次就找到倒数第k个节点，时间复杂度为O(n)，空间复杂度为O(1)，是比较优秀的解决方法。