算法设计题：head指向一单链表，请编写算法在单链表中每个data域为S的结点前插入一个data域为T的新结点。 1)给出算法的基本思想。 (2)用c++写出算法，并对算法中的关键步骤适当注释。 (3)给出算法的时间和空间复杂度。

(1) 基本思路：
这个题目要求我们在给定的单链表中，找到所有值为 S 的节点，并在它们之前插入一个新的值为 T 的节点。我们可以遍历整个链表，对于每个值为 S 的节点，创建一个新的节点，并将其指向前一个节点，然后将当前节点指向新的节点。这样，新节点就在原节点前面了。

(2) C++ 实现：

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct ListNode {
    int data;
    ListNode* next;
};

// 插入函数
void insertBeforeNode(ListNode* head, int S, int T) {
    ListNode* newNode = new ListNode(); // 创建新节点
    newNode->data = T; // 新节点数据赋值为T

    if(head == nullptr || head->data != S) { // 如果头节点为空或者不是S，直接连接
        newNode->next = head;
        head = newNode;
    } else { // 否则从头开始查找S节点
        ListNode* current = head;
        while(current->next != nullptr && current->next->data != S) {
            current = current->next;
        }
        if(current->next != nullptr) { // 找到S节点，插入新节点
            newNode->next = current->next;
            current->next = newNode;
        }
    }

    // 释放旧头节点的内存，如果需要
    delete head;
}

// 测试函数
void printList(ListNode* head) {
    while(head) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // 初始化链表示例
    ListNode* head = new ListNode{7, new ListNode{5, new ListNode{3, new ListNode{2, new ListNode{1}}}}};
    insertBeforeNode(head, 5, 6);
    printList(head); // 输出：1 -> 2 -> 3 -> 6 -> 5 -> 7 -> NULL

    return 0;
}

关键步骤注释：首先检查头节点是否满足条件，如果不满足，则直接链接新节点；否则进入循环，在找到第一个值为 S 的节点时停止，然后插入新节点。

(3) 时间和空间复杂度：
- 时间复杂度：O(n)，其中 n 是链表的长度，因为可能需要遍历整个链表一次。
- 空间复杂度：O(1)，除了创建新节点的空间之外，没有额外的存储需求。但如果链表非常长，创建新节点可能会占用较多的临时栈空间，此时空间复杂度可以视为 O(n)。