动态存贮

【描述】创建 n 个节点的单向链表，按顺序存储 1~n 。请用动态分配内存的方式创建节点。遍历输出每个节点的值。
【输入格式】一个正整数n
【输出格式】输出单向链表每个节点的值，数值之间用空格隔开。
【输入样例】10
【输出样例】1 2 3 4 5 6 7 8 9

#include<iostream>
using namespace std;

struct node{
	int data;    // 数据 
	node *next;  // 指向后继节点的指针 
}; 

int main(){
	int n;
	cin >> n;
	// 1、创建第一个节点，头指针指向这个节点 
	node *head = new node; // 动态分配内存 
	head->data = 1;        //新结点的数据
	head->next = NULL;     //初始化指针 
 
 	// 2、插入值为2~n的新节点(在尾部插入)
 	int i = 2;
	node *p = head; // 新节点总是插入p后一个位置 
	for(int i = 2; i < n ;i++){
		// 分配新结点s
		node *s = new node; 
		s->data = i;       // 新结点存储数字i
		s->next = NULL;    //初始化指针
		// 把s插入p后面 
		p->next = s;
		// p后移1 
		p = p->next;
	}
	
	// 3、正序遍历输出
	p = head; //p指向头节点
	while(p != NULL){
		cout << p->data << ' ';
		p = p->next; // 指向后继节点 
	}
	cout << endl;
 	return 0; 
}

/*
【输入用例2】
1
【输出用例2】
1
【输入用例3】
3
【输出用例3】
1 2
【输入用例4】
5
【输出用例4】
1 2 3 4
【输入用例5】
20
【输出用例5】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
【输入用例6】
99
【输出用例6】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 
*/

双向链表创建

【描述】创建一个包含整数的双向链表，自定义输入双向链表的元素个数与元素，输出最后的循环链表元素。
【输入描述】
输入为两行，第一行表示元素个数n，其中n>0,第二行表示n个元素
【输出描述】
输出最后的循环链表元素
【样例输入】
5
1 2 3 4 5
【样例输出】
循环链表元素: 1 2 3 4 5

#include <iostream>  
using namespace std; 

// 定义循环链表的节点结构体
struct Node {
    int data;      
    Node* next;    
};

// 功能：根据给定数组创建循环链表
// 参数：arr - 存储数据的整型数组；n - 数组的大小（节点数量）
// 返回值：循环链表的头节点指针（若n=0则返回nullptr）
Node* createCircularList(int arr[], int n) 
{
    if(n == 0) return nullptr;  // 处理空数组情况：无节点时返回空指针
    
    // 创建头节点：数据为数组第一个元素，next初始化为空
    Node* head = new Node{arr[0], nullptr};
    Node* tail = head;  // 尾指针初始指向头节点（后续会移动到最后一个节点）
    
    // 从数组第二个元素开始，依次创建新节点并连接到链表尾部
    for(int i=1; i<n; i++) {
        tail->next = new Node{arr[i], nullptr};  // 创建新节点，数据为当前数组元素，next暂为空
        tail = tail->next;                       // 尾指针移动到新节点（成为新的尾节点）
    }
    
    tail->next = head;  // 关键操作：将尾节点的next指向头节点，形成循环链表
    return head;        // 返回链表的头节点
}

// 功能：遍历循环链表并输出所有节点的数据
// 参数：head - 循环链表的头节点指针
void traverseCircular(Node* head) {
    if(!head) return;  // 空链表直接返回（无节点可遍历）
    
    Node* p = head;    // 定义游标指针p，初始指向头节点
    do {
        cout << p->data << " ";  // 输出当前节点的数据
        p = p->next;             // 游标指针移动到下一个节点
    } while(p != head);  // 循环终止条件：游标回到头节点（确保遍历完整个环）
    cout << endl;        // 输出换行符，格式化显示
}

int main() {
    int n;
    cin >> n;  // 输入数组的大小（即循环链表的节点数量）
    
    int* arr = new int[n];  // 动态分配数组内存（存储用户输入的数值）
    for(int i = 0; i < n; i++) {  // 循环读取n个整数，存入数组
        cin >> arr[i];
    }
    
    Node* list = createCircularList(arr, n);  // 调用函数创建循环链表
    cout << "循环链表元素: ";
    traverseCircular(list);  // 调用函数遍历并输出循环链表的所有元素
       
    return 0;
}

/*
【输入用例2】
1
5
【输出用例2】
循环链表元素: 5 
【输入用例3】
3
10 20 30
【输出用例3】
循环链表元素: 10 20 30 
【输入用例4】
8
1 2 3 4 5 6 7 8
【输出用例4】
循环链表元素: 1 2 3 4 5 6 7 8 
【输入用例5】
0
【输出用例5】
循环链表元素: 
【输入用例6】
6
9 8 7 6 5 4
【输出用例6】
循环链表元素: 9 8 7 6 5 4 
*/

合并循环链表

【描述】将两个升序循环链表合并为新的循环链表，然后将循环链表输出。
【输入描述】输入为四行，第一行代表第一个链表输入元素的个数n1，第二行输入n1个元素；
第三行代表第二个链表输入元素的个数n2，第四行输入n2个元素；（n1与n2均大于0）
【输出描述】
输出合并后的链表元素，按照元素大小顺序排列
【样例输入】
5
1 2 3 4 5
3
1 2 3
【样例输出】
合并后的循环链表: 1 1 2 2 3 3 4 5

#include <iostream>
using namespace std;

// 定义循环链表节点结构体（不使用头节点）
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// 合并两个有序循环链表的函数
Node* mergeCircularLists(Node* list1, Node* list2) {
    if (!list1) return list2;
    if (!list2) return list1;

    // 找到list1和list2的尾节点
    Node* tail1 = list1;
    while (tail1->next != list1) {
        tail1 = tail1->next;
    }

    Node* tail2 = list2;
    while (tail2->next != list2) {
        tail2 = tail2->next;
    }

    // 断开循环，形成两个有序的非循环链表
    tail1->next = nullptr;
    tail2->next = nullptr;

    // 创建一个新的头节点
    Node* newHead = new Node(-1); // 哨兵节点
    Node* tail = newHead;

    Node* p = list1;
    Node* q = list2;

    // 合并过程
    while (p && q) {
        if (p->data <= q->data) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;
    }

    // 处理剩余节点
    if (p) {
        tail->next = p;
    } else {
        tail->next = q;
    }

    // 找到新链表的尾节点
    Node* newTail = tail;
    while (newTail->next) {
        newTail = newTail->next;
    }

    // 形成新的循环链表
    newTail->next = newHead->next;

    // 删除哨兵节点
    Node* temp = newHead;
    newHead = newHead->next;
    delete temp;

    return newHead; // 返回新循环链表的头节点
}

// 创建循环链表（不使用头节点）
Node* createCircularList(int arr[], int n)
{
    if (n == 0) return nullptr;
    Node* head = new Node(arr[0]);
    Node* tail = head;
    for (int i = 1; i < n; i++) {
        tail->next = new Node(arr[i]);
        tail = tail->next;
    }
    tail->next = head;  // 形成循环
    return head;
}

// 打印循环链表
void printCircularList(Node* head) 
{
    if (!head) return;
    Node* p = head;
    do {
        cout << p->data << " ";
        p = p->next;
    } while (p != head);
    cout << endl;
}

// 手动输入数组并创建循环链表
Node* createCircularListFromInput(int n) {
    if (n <= 0) return nullptr;
    
    int* arr = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    Node* head = createCircularList(arr, n);
    delete[] arr; // 释放临时数组内存
    return head;
}

int main() 
{
    int n1, n2;
    
    // 输入第一个链表
    cin >> n1;
    Node* list1 = createCircularListFromInput(n1);
    // 输入第二个链表
    cin >> n2;
    Node* list2 = createCircularListFromInput(n2);
    
    // 合并并打印结果
    Node* merged = mergeCircularLists(list1, list2);
    cout << "合并后的循环链表: ";
    printCircularList(merged);

    return 0;
}

/*
【输入用例2】
1
1
1
2
【输出用例2】
合并后的循环链表: 1 2 
【输入用例3】
3
1 3 5
2
2 4
【输出用例3】
合并后的循环链表: 1 2 3 4 5 
【输入用例4】
2
1 2
2
3 4
【输出用例4】
合并后的循环链表: 1 2 3 4 
【输入用例5】
0

3
10 20 30
【输出用例5】
合并后的循环链表: 10 20 30 
【输入用例6】
4
5 10 15 20
3
6 12 18
【输出用例6】
合并后的循环链表: 5 6 10 12 15 18 20 
*/

约瑟夫环问题

【描述】约瑟夫环问题是一个经典的数学问题，描述如下：N个人围成一圈，从某个指定的人开始报数，数到K的那个人就被淘汰，接着下一个人重新从1开始报数，直到所有人都被淘汰。请你用链表相关知识求最后一个幸存者的初始位置。
【输入描述】输入两个数n与m，其中n表示人数，m表示间隔
【输出描述】输出最后剩下的人号码
【样例输入】
10 2
【样例输出】
最后剩下的人是: 5

#include <iostream>
using namespace std;

// 定义循环链表节点结构体
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// 创建循环链表
Node* createCircularList(int n) {
    if (n == 0) return nullptr;
    Node* head = new Node(1);  // 创建头节点
    Node* tail = head;
    for (int i = 2; i <= n; i++) {
        tail->next = new Node(i);
        tail = tail->next;
    }
    tail->next = head;  // 尾节点指向头节点形成环
    return head;
}

// 约瑟夫环问题求解函数
int josephus(Node*& head, int m) {
    if (!head) return -1;  // 空链表直接返回-1
    Node* p = head;
    // 找到尾节点，用于判断循环结束
    Node* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    // 模拟淘汰过程
    while (p->next != p) {  // 当链表中只剩一个节点时结束
        // 移动m-1步找到要淘汰的节点
        for (int i = 1; i < m; i++) {
            p = p->next;
            tail = tail->next;  // 尾节点同步移动
        }
        // 淘汰当前节点
        Node* tmp = p->next;
        p->data = tmp->data;  // 用下一个节点的数据覆盖当前节点
        p->next = tmp->next;  // 跳过下一个节点
        delete tmp;  // 释放被淘汰节点的内存
        // 如果淘汰的是尾节点，需要更新尾节点
        if (tmp == tail) {
            tail = p;
        }
    }
    int res = p->data;  // 最后剩下的节点数据
    delete p;  // 释放最后一个节点
    return res;
}

// 打印循环链表（用于调试）
void printCircularList(Node* head) {
    if (!head) return;
    Node* p = head->next;
    while (p != head) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    int n, m;
    cin >> n >> m;//输入人数n和间隔m

    // 创建循环链表
    Node* list = createCircularList(n);
    // 求解约瑟夫环问题
    int lastPerson = josephus(list, m);
    cout << "最后剩下的人是: " << lastPerson << endl;

    return 0;
}

/*
【输入用例2】
1 1
【输出用例2】
最后剩下的人是: 1
【输入用例3】
5 2
【输出用例3】
最后剩下的人是: 3
【输入用例4】
7 3
【输出用例4】
最后剩下的人是: 4
【输入用例5】
10 1
【输出用例5】
最后剩下的人是: 10
【输入用例6】
6 4
【输出用例6】
最后剩下的人是: 5
*/

删除双向链表倒数第k个节点

【描述】自定义设计一个程序，将双向链表中某一个元素删除后，然后将该链表元素正向、反向输出。
【输入描述】输入分三行，第一行表示输入双向链表的元素个数（n,n>0），第二行输入n个整数（用空格分隔），第三行输入要删除的倒数第k个节点的k值
【输出描述】
分别输出删除后的正向与反向的链表元素
【样例输入1】
5
1 2 3 4 5
2
【样例输出1】
正向: 1 2 3 5
反向: 5 3 2 1
【样例输入2】
5
1 2 3 4 5
6
【样例输出2】
k值超过链表长度，无法删除
正向: 1 2 3 4 5
反向: 5 4 3 2 1

#include <iostream>
using namespace std;

// 定义双向链表节点结构体
struct DNode {
    int data;
    DNode* prev;
    DNode* next;
    DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 删除双向链表倒数第k个节点的函数
void deleteKthFromEnd(DNode*& head, int k) {
    if (!head || k <= 0) return;  // 处理空链表或无效k值

    DNode* fast = head->next;  // 从第一个实际节点开始
    DNode* slow = head->next;
    DNode* tail = head->prev;  // 获取尾节点

    // 快指针先走k步
    for (int i = 0; i < k; i++) {
        fast = fast->next;
        if (fast == head) {  // k超过链表长度
            cout << "k值超过链表长度，无法删除" << endl;
            return;
        }
    }

    // 同时移动快慢指针，直到快指针回到头节点
    while (fast != head) {
        fast = fast->next;
        slow = slow->next;
    }

    // 删除slow节点
    if (slow == head->next) {  // 如果要删除的是第一个实际节点
        head->next = slow->next;
        slow->next->prev = head;
    } else if (slow == tail) {  // 如果要删除的是最后一个节点
        tail = slow->prev;
        tail->next = head;
        head->prev = tail;
    } else {  // 删除中间节点
        slow->prev->next = slow->next;
        slow->next->prev = slow->prev;
    }
    delete slow;  // 释放被删除节点的内存
}

// 创建双向链表（带头节点）
DNode* createDoublyList(int arr[], int n)
{
    if (n == 0) return nullptr;
    DNode* head = new DNode(-1);  // 哨兵节点
    DNode* tail = head;
    for (int i = 0; i < n; i++)
    {
        DNode* newNode = new DNode(arr[i]);
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    tail->next = head;  // 形成循环
    head->prev = tail;  // 头节点指向尾节点
    return head;
}

// 手动输入创建双向链表
DNode* createDoublyListFromInput() {
    int n;
    cin >> n;//输入双向链表的元素个数
    
    DNode* head = new DNode(-1);  // 哨兵节点
    DNode* tail = head;
    
    for (int i = 0; i < n; i++) //输入 n 个整数（用空格分隔）
    {
        int val;
        cin >> val;
        DNode* newNode = new DNode(val);
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    
    tail->next = head;  // 形成循环
    head->prev = tail;  // 头节点指向尾节点
    return head;
}

// 打印双向链表（从前往后）
void printForward(DNode* head) 
{
    if (!head || head->next == head) {  // 空链表或只有哨兵节点
        cout << "链表为空" << endl;
        return;
    }
    DNode* p = head->next;
    cout << "正向: ";
    while (p != head) 
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 打印双向链表（从后往前）
void printBackward(DNode* head) 
{
    if (!head || head->prev == head) {  // 空链表或只有哨兵节点
        cout << "链表为空" << endl;
        return;
    }
    DNode* p = head->prev;
    cout << "反向: ";
    while (p != head) 
    {
        cout << p->data << " ";
        p = p->prev;
    }
    cout << endl;
}

int main() 
{
    // 手动输入创建双向链表
    DNode* list = createDoublyListFromInput();
    
    int k;
    cin >> k;//输入要删除的倒数第k个节点的k值
    
    // 删除并打印结果
    deleteKthFromEnd(list, k);
    printForward(list);
    printBackward(list);

    return 0;
}

/*
【输入用例2】
1
10
1
【输出用例2】
k值超过链表长度，无法删除
正向: 10 
反向: 10 
【输入用例3】
3
1 2 3
1
【输出用例3】
正向: 1 2 
反向: 2 1 
【输入用例4】
4
10 20 30 40
2
【输出用例4】
正向: 10 20 40 
反向: 40 20 10 
【输入用例5】
5
5 4 3 2 1
5
【输出用例5】
k值超过链表长度，无法删除
正向: 5 4 3 2 1 
反向: 1 2 3 4 5 
【输入用例6】
3
7 8 9
5
【输出用例6】
k值超过链表长度，无法删除
正向: 7 8 9 
反向: 9 8 7 
*/