链表存储数据

【描述】创建一个链表，按顺序存储字母A’~‘E’。从第一个结点依次输出链表中的数据。
【输入描述】无
【输出描述】按顺序存储字母A’~‘E’
【样例输入】无
【样例输出】ABCDE

#include<iostream>
using namespace std;

struct node{
	char data;   // 数据 
	node *next;  // 指针 
}; 

int main(){
	// 创建节点 
	node n1 = {'A', NULL};  
	node n2 = {'B', NULL};  
	node n3 = {'C', NULL};  
	node n4 = {'D', NULL};
	node n5 = {'E', NULL};
	// 建立连接 n1->n2->n3->n4->n5 
	n1.next = &n2;
	n2.next = &n3;
	n3.next = &n4;
	n4.next = &n5;
	
	node *head = &n1; // 指向头节点 
	while( head != NULL){
		cout << head->data;
		head = head->next; 
	} 
	cout << endl; 

	return 0;
}

//本题没有更多的测试用例

链表反转

【描述】输入一个你喜欢的链表，然后将这个链表打印出来，同时反转输出原链表
【输入描述】输入为一行，表示将要输入链表中元素，输入的数字必须为整数；当输入完毕时以“-1”结尾，表示输入完毕
【输出描述】输出原链表与反转后链表
【样例输入】
-2 2 0 4 5 -1
【样例输出】
原链表: -2 -> 2 -> 0 -> 4 -> 5
反转后链表: 5 -> 4 -> 0 -> 2 -> -2

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct Node 
{
    int data;       
    Node* next;    
    // 构造函数，用于初始化节点值和指针
    Node(int val) : data(val), next(nullptr) {}
};

// 反转链表的函数（迭代法实现）
Node* reverseList(Node* head) 
{
    Node* prev = nullptr;    // 前驱节点指针，初始化为空
    Node* curr = head;       // 当前节点指针，初始化为头节点
    // 遍历链表直到当前节点为空
    while (curr)
    {
        Node* nextTemp = curr->next;  // 保存下一个节点地址
        curr->next = prev;            // 将当前节点指针指向前驱节点
        prev = curr;                  // 前驱指针移动到当前节点
        curr = nextTemp;              // 当前指针移动到下一个节点
    }
    return prev;  // 返回新头节点（原链表的尾节点）
}

// 打印链表的辅助函数
// 功能：按顺序输出链表元素，节点间用" -> "连接
void printList(Node* head) 
{
    Node* p = head;  // 临时指针用于遍历
    while (p) 
    {
        cout << p->data;  // 输出当前节点值
        if (p->next)      // 如果非尾节点，添加连接符
            cout << " -> ";
        p = p->next;      // 移动到下一个节点
    }
    cout << endl;  // 输出换行符
}

// 通过手动输入创建链表
// 输入规则：输入整数序列，以-1作为结束标志
Node* createListFromInput() {
    Node* head = nullptr;  
    Node* tail = nullptr;  
    int val;               // 临时存储输入值

   //输入链表元素（输入-1结束）"
    while (true) {
        cin >> val; 
        if (val == -1) break;  // 输入-1时终止循环
        
        // 创建新节点并初始化
        Node* newNode = new Node(val);
        if (!head) {  // 如果链表为空
            head = tail = newNode;  // 新节点作为头节点和尾节点
        } else {      // 链表非空时
            tail->next = newNode;   // 原尾节点指向新节点
            tail = newNode;         // 更新尾节点为新节点
        }
    }
    return head;  // 返回链表头指针
}

int main()
{
    // 手动输入创建链表
    Node* head = createListFromInput();
    
    // 输出原始链表内容
    cout << "原链表: ";
    printList(head);

    // 反转链表操作
    Node* reversedHead = reverseList(head);

    // 输出反转后的链表内容
    cout << "反转后链表: ";
    printList(reversedHead);
    
    return 0;
}

/*
【输入用例2】
1 1 1 1 1 1 1 -1
【输出用例2】
原链表: 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1
反转后链表: 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1
【输入用例3】
-2 -3 -4 -5 -6 -7 -8 -1
【输出用例3】
原链表: -2 -> -3 -> -4 -> -5 -> -6 -> -7 -> -8
反转后链表: -8 -> -7 -> -6 -> -5 -> -4 -> -3 -> -2
【输入用例4】
-2 -3 -4 0 2 3 4 -1
【输出用例4】
原链表: -2 -> -3 -> -4 -> 0 -> 2 -> 3 -> 4
反转后链表: 4 -> 3 -> 2 -> 0 -> -4 -> -3 -> -2
【输入用例5】
10 20 30 40 50 60 -1
【输出用例5】
原链表: 10 -> 20 -> 30 -> 40 -> 50 -> 60
反转后链表: 60 -> 50 -> 40 -> 30 -> 20 -> 10
【输入用例6】
0 -1
【输出用例6】
原链表: 0
反转后链表: 0
*/

合并两个有序链表

【描述】将两个有序的链表合并后输出，链表1与链表2所有的元素均输出，无论是否在重复数字
【输入描述】输入为两行，第一行表示第一个链表数据，以“-1”结尾表示输入完毕；第二行表示第二个链表数据，以“-1”结尾表示输入完毕
【输出描述】输出合并后的链表
【样例输入】
-2 0 1 4 5 -1
-3 -2 0 3 6 -1
【样例输出】
第一个链表：-2 -> 0 -> 1 -> 4 -> 5
第二个链表：-3 -> -2 -> 0 -> 3 -> 6
合并后链表: -3 -> -2 -> -2 -> 0 -> 0 -> 1 -> 3 -> 4 -> 5 -> 6

#include <iostream>
using namespace std;

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

// 合并两个有序链表的函数（保持升序）
Node* mergeTwoLists(Node* l1, Node* l2) {
    Node dummy(0);
    Node* tail = &dummy;

    while (l1 && l2) {
        if (l1->data < l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

// 打印链表
void printList(Node* head) {
    Node* p = head;
    while (p) {
        cout << p->data;
        if (p->next) cout << " -> ";
        p = p->next;
    }
    cout << endl;
}

// 手动输入创建链表（以-1结束）
Node* createLinkedList() {
    Node* head = nullptr;
    Node* tail = nullptr;
    int val;

   //输入链表元素（输入-1结束）
    while (true) {
        cin >> val;
        if (val == -1) break;

        Node* newNode = new Node(val);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

int main() {
    //创建第一个有序链表
    Node* l1 = createLinkedList();

    //创建第二个有序链表
    Node* l2 = createLinkedList();

    cout << "第一个链表：";
    printList(l1);
    cout << "第二个链表：";
    printList(l2);

    Node* merged = mergeTwoLists(l1, l2);
    cout << "合并后链表: ";
    printList(merged);

    return 0;
}

/*
【输入用例2】
 0 1 4 5 -1
-3 -2 0  -1
【输出用例2】
第一个链表：0 -> 1 -> 4 -> 5
第二个链表：-3 -> -2 -> 0
合并后链表: -3 -> -2 -> 0 -> 0 -> 1 -> 4 -> 5
【输入用例3】
1 2 3 4 -1
-3 -2 0 1  -1
【输出用例3】
第一个链表：1 -> 2 -> 3 -> 4
第二个链表：-3 -> -2 -> 0 -> 1
合并后链表: -3 -> -2 -> 0 -> 1 -> 1 -> 2 -> 3 -> 4
【输入用例4】
9 9 9 9 9  -1
0 0 0 0 0  -1
【输出用例4】
第一个链表：9 -> 9 -> 9 -> 9 -> 9
第二个链表：0 -> 0 -> 0 -> 0 -> 0
合并后链表: 0 -> 0 -> 0 -> 0 -> 0 -> 9 -> 9 -> 9 -> 9 -> 9
【输入用例5】
10 20 30 40 -1
-9 -9 -9 -9 -1
【输出用例5】
第一个链表：10 -> 20 -> 30 -> 40
第二个链表：-9 -> -9 -> -9 -> -9
合并后链表: -9 -> -9 -> -9 -> -9 -> 10 -> 20 -> 30 -> 40
【输入用例6】
-5  -1
0 -1
【输出用例6】
第一个链表：-5
第二个链表：0
合并后链表: -5 -> 0
*/

链表是否有环

【描述】链表是否有环的含义是指链表中是否存在一个节点，其next指针指向链表中之前的某个节点，从而形成闭合的循环结构。这种情况会导致遍历链表时进入无限循环，无法正常终止。现在要求你设计一个程序判断输入的链表数据是否有环。
【输入描述】
输入为两行，第一行表示链表数据，以“-1”结尾表示输出完毕
第二行表示输入环入口位置（从0开始，-1表示无环）
【输出描述】
输出链表的检测结果是否有环，以及环的位置
【样例输入1】
1 2 3 4 5 6 7-1
1
【样例输出1】
链表检测结果: 有环（环入口在位置 1）
【样例输入2】
2 5 6 7 8 -1
6
【样例输出2】
链表检测结果: 无环

#include <iostream>
#include <vector>
using namespace std;

// 定义链表节点结构体
struct ListNode {
    int val;            // 节点存储的值
    ListNode* next;     // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数
};

// 判断链表是否有环的核心函数（快慢指针法）
bool hasCycle(ListNode* head) {
    if (!head || !head->next) return false;  // 空链表或单节点无环
    ListNode* slow = head;  // 慢指针（每次移动一步）
    ListNode* fast = head;  // 快指针（每次移动两步）
    while (fast && fast->next) {  // 快指针需至少两步移动空间
        slow = slow->next;        // 慢指针移动一步
        fast = fast->next->next;  // 快指针移动两步
        if (slow == fast) return true;  // 相遇则存在环
    }
    return false;  // 快指针到末尾则无环
}

// 手动输入创建链表（带环检测）
pair<ListNode*, int> createLinkedList() {
    vector<int> elements;  // 存储链表元素
    int val;
    // 输入链表元素（输入-1结束）
    while (cin >> val) {
        if (val == -1) break;
        elements.push_back(val);
    }
    
    // 创建链表
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    for (int num : elements) {
        ListNode* newNode = new ListNode(num);
        if (!head) {
            head = tail = newNode;  // 首节点初始化
        } else {
            tail->next = newNode;   // 尾插法连接节点
            tail = newNode;
        }
    }
    
    // 处理环结构
    int pos;
    cin >> pos;  // 输入环入口位置（从0开始，-1表示无环）
    if (pos >= 0 && pos < elements.size()) {
        ListNode* cycleNode = head;
        for (int i = 0; i < pos; ++i) cycleNode = cycleNode->next;  // 定位环入口节点
        tail->next = cycleNode;  // 尾节点指向环入口形成环
        return {head, pos};      // 返回链表头和环入口位置
    }
    return {head, -1};  // 无环
}

int main() {
    // 创建第一个链表并检测环
    auto [list1, pos1] = createLinkedList();
    cout << "链表检测结果: " << (hasCycle(list1) ? "有环" : "无环") 
         << (pos1 != -1 ? "（环入口在位置 " + to_string(pos1) + "）" : "") << endl;
    return 0;
}

/*
【输入用例2】
-1
-1
【输出用例2】
链表检测结果: 无环
【输入用例3】
5 -1
【输出用例3】
链表检测结果: 无环
【输入用例4】
7 -1
0
【输出用例4】
链表检测结果: 有环（环入口在位置 0）
【输入用例5】
1 2 3 4 5 -1
-1
【输出用例5】
链表检测结果: 无环
【输入用例6】
3 5 7 9 2 -1
2
【输出用例6】
链表检测结果: 有环（环入口在位置 2）
*/

链表的插入操作

【描述】小张同学最近刚学完链表相关知识，他想设计一个程序能够根据情况往链表中插入元素，比如链表头、中间或者链表尾。现在请你帮助他完成这个作品。
【输入描述】
输入为两行，第一行为a,b两个数字，其中a数字表示需要插入的位置，b数字表示插入的值
第二行输入链表数据，以“-1”结尾表示输入完毕；如果插入的位置超过链表长度，则执行在尾部插入。
【输出描述】输出插入后的链表数据
【样例输入1】
0 3
1 2 3 4 5 -1
【样例输出1】
插入位置0后: 3 -> 1 -> 2 -> 3 -> 4 -> 5
【样例输入2】
6 3
1 2 3 4 5 -1
【样例输出2】
插入位置超出链表长度，执行尾部插入
插入位置6后: 1 -> 2 -> 3 -> 4 -> 5 -> 3

#include <iostream>
#include <vector>
using namespace std;

// 定义链表节点结构体
struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 在指定位置插入节点的函数（保持原逻辑）
ListNode* insertNode(ListNode* head, int index, int value) {
    ListNode* newNode = new ListNode(value);
    
    if (index == 0) {
        newNode->next = head;
        return newNode;
    }
    
    ListNode* current = head;
    for (int i = 0; i < index - 1 && current != nullptr; ++i) {
        current = current->next;
    }
    
    if (current == nullptr) {
        cout << "插入位置超出链表长度，执行尾部插入" << endl;
        current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    } else {
        newNode->next = current->next;
        current->next = newNode;
    }
    
    return head;
}

// 手动输入创建链表（带环检测）
ListNode* createLinkedList() {
    vector<int> elements;
    int val;
    //输入链表元素（输入-1结束）
    while (cin >> val) {
        if (val == -1) break;
        elements.push_back(val);
    }
    
    // 创建链表
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    for (int num : elements) {
        ListNode* newNode = new ListNode(num);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    
    return head;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        cout << current->val;
        if (current->next != nullptr) cout << " -> ";
        current = current->next;
    }
}

int main() {    
    int a,b;//a表示插入的
    cin >> a >> b;
    // 手动输入创建链表
    ListNode* head = createLinkedList();
   
    head = insertNode(head, a, b);  // 插入操作
    cout << "插入位置" << a << "后: ";
    printList(head); 
    
    return 0;
}

/*
【输入用例2】
3 6
0 0 0 0 0 0 -1
【输出用例2】
插入位置3后: 0 -> 0 -> 0 -> 6 -> 0 -> 0 -> 0
【输入用例3】
0 99
1 2 -2 -3 -1
【输出用例3】
插入位置0后: 99 -> 1 -> 2 -> -2 -> -3
【输入用例4】
7 0
0 1 -3 9 -25 65 -1
【输出用例4】
插入位置超出链表长度，执行尾部插入
插入位置7后: 0 -> 1 -> -3 -> 9 -> -25 -> 65 -> 0
【输入用例5】
0 1
-1
【输出用例5】
插入位置0后: 1
【输入用例6】
5 5
0 1 2 3 4 -1
【输出用例6】
插入位置5后: 0 -> 1 -> 2 -> 3 -> 4 -> 5
*/