单链表复制算法：空间复杂度O(1)实现

本文介绍一种单链表复制算法，该算法的空间复杂度为O(1)，即不使用额外的空间来存储复制后的链表。

算法设计思想

算法的基本设计思想是在单链表类中增加一个名为copy(L)的功能，实现单链表的复制。要求算法的空间复杂度为O(1)，即不使用额外的空间来存储复制后的链表。

C++代码实现

#include <iostream>

class ListNode {
public:
    int val;
    ListNode* next;

    ListNode(int value) {
        val = value;
        next = nullptr;
    }
};

class LinkedList {
private:
    ListNode* head;

public:
    LinkedList() {
        head = nullptr;
    }

    void insert(int value) {
        ListNode* newNode = new ListNode(value);
        if (head == nullptr) {
            head = newNode;
        }
        else {
            ListNode* curr = head;
            while (curr->next != nullptr) {
                curr = curr->next;
            }
            curr->next = newNode;
        }
    }

    LinkedList copy() {
        LinkedList newList;
        ListNode* curr = head;

        while (curr != nullptr) {
            newList.insert(curr->val);  // 复制当前节点的值并插入到新链表中
            curr = curr->next;
        }

        return newList;
    }

    void display() {
        ListNode* curr = head;
        while (curr != nullptr) {
            std::cout << curr->val << ' ';
            curr = curr->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    LinkedList list1;
    list1.insert(1);
    list1.insert(2);
    list1.insert(3);

    LinkedList list2 = list1.copy();  // 复制list1到list2
    list2.display();

    return 0;
}

关键代码注释

ListNode类表示链表的节点，包含一个整数值和指向下一个节点的指针。
LinkedList类表示链表，包含一个指向头节点的指针。
insert()函数用于向链表中插入一个新节点，如果链表为空则将新节点设为头节点，否则找到链表的尾节点插入新节点。
copy()函数创建一个新的链表newList，遍历原始链表，将每个节点的值复制并插入到newList中。
display()函数用于打印链表中的元素。

空间复杂度分析

该算法的空间复杂度为O(1)，因为仅使用了有限的额外空间来存储新链表的节点，而不是使用额外的数据结构。

总结

本文介绍了一种单链表复制算法，该算法的空间复杂度为O(1)，并且给出了C++代码实现和关键代码注释。该算法简洁高效，适用于需要在有限空间内复制单链表的场景。