第1关：实现链表结点

链表是一种数据结构，由一组节点（node）组成，每个节点包含两部分，一部分是数据，另一部分是指向下一个节点的指针。下面是一个链表节点的实现示例，使用 Python 语言：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

在这个实现中，每个节点包含一个 val 属性，用于存储节点的值，以及一个 next 属性，用于指向下一个节点。节点的值可以是任何类型，包括整数、字符串或自定义对象，next 属性可以是 None 或指向另一个 ListNode 对象。

可以使用以下代码创建一个链表节点：

node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)

node1.next = node2
node2.next = node3

这个代码片段创建了三个节点，分别赋值为 1、2 和 3，然后将它们按顺序连接起来，形成一个链表。

相关问题

第9关：查找链表倒数第k个结点

题目描述：给定一个链表，输出该链表倒数第k个节点，如果k大于链表长度则返回空。

算法思路：使用双指针，先让第一个指针移动k-1个节点，然后再让第一个指针和第二个指针同时移动，当第一个指针到达链表结尾时，第二个指针指向的就是倒数第k个节点。

参考代码实现（Python）：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def findKthToTail(head, k):
    if head is None or k <= 0:
        return None
    
    # 定义两个指针，初始都指向头结点
    p1 = p2 = head
    
    # 让第一个指针移动k-1个节点
    for i in range(k-1):
        if p1.next is None:
            return None
        p1 = p1.next
    
    # 两个指针同时移动，直到第一个指针到达链表结尾
    while p1.next is not None:
        p1 = p1.next
        p2 = p2.next
    
    return p2

参考代码实现（Java）：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public ListNode findKthToTail(ListNode head, int k) {
    if (head == null || k <= 0) {
        return null;
    }
    
    // 定义两个指针，初始都指向头结点
    ListNode p1 = head;
    ListNode p2 = head;
    
    // 让第一个指针移动k-1个节点
    for (int i = 0; i < k-1; i++) {
        if (p1.next == null) {
            return null;
        }
        p1 = p1.next;
    }
    
    // 两个指针同时移动，直到第一个指针到达链表结尾
    while (p1.next != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    
    return p2;
}

第1关：静态链表及其创建

静态链表是一种使用数组实现的链表数据结构，它通过数组中的元素来存储链表的结点，并使用一个指针来表示下一个结点的位置。在静态链表中，每个元素都包含两个部分：数据部分和指针部分。

在创建静态链表时，需要定义一个数组来存储链表的结点，同时需要定义一个变量来表示链表的头结点。头结点通常不包含有效数据，其指针部分指向链表的第一个结点。同时，数组中的每个元素都需要包含一个指针部分，用于指向下一个结点的位置。

下面是一个简单的静态链表创建的示例代码：

#include <stdio.h>

// 定义链表结点
typedef struct Node {
    int data;  // 数据部分
    int next;  // 指针部分
} Node;

// 静态链表创建函数
int createList(Node list[], int n) {
    int head = 0;   // 头结点位置
    int i;

    // 初始化链表
    for (i = 0; i < n; i++) {
        list[i].next = -1;
    }

    // 读入链表数据
    for (i = 0; i < n; i++) {
        scanf("%d", &list[i].data);
    }

    // 链表头结点指向第一个结点
    if (n > 0) {
        head = 0;
        list[head].next = 1;
    }

    // 设置结点的指针部分
    for (i = 1; i < n; i++) {
        list[i].next = i + 1;
    }

    // 最后一个结点指向空
    if (n > 0) {
        list[n-1].next = -1;
    }

    return head;
}

int main() {
    Node list[100];
    int n, head, i;

    // 读入链表长度
    scanf("%d", &n);

    // 创建链表
    head = createList(list, n);

    // 输出链表内容
    i = head;
    while (i != -1) {
        printf("%d ", list[i].data);
        i = list[i].next;
    }
    printf("\n");

    return 0;
}

在上面的代码中，我们定义了一个 `Node` 结构体来表示链表的结点，其中包含数据部分和指针部分。我们还定义了一个 `createList` 函数来创建静态链表，该函数接受一个数组和一个整数作为参数，分别表示链表的存储空间和链表的长度。在函数中，我们首先初始化链表，然后读入链表数据，并设置链表结点的指针部分。最后，我们返回头结点的位置。

在 `main` 函数中，我们首先读入链表的长度，然后调用 `createList` 函数创建链表。最后，我们输出链表的内容。