设计算法将单链表L就地转置

单链表就地转置的算法如下：

1. 定义三个指针：p、q、r。
2. p 指向链表的头结点，q 指向头结点的下一个节点，r 指向 q 的下一个节点。
3. 将头结点的 next 指针置为空。
4. 从 q 开始遍历链表，每遍历到一个节点，就将该节点的 next 指针指向 p，然后依次向后移动三个指针，即 p=q，q=r，r=r->next。
5. 遍历结束后，将原链表的尾结点指向 p。

实现代码如下：

void reverseList(ListNode *head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    ListNode *p = head;
    ListNode *q = head->next;
    ListNode *r = q->next;
    p->next = nullptr;
    while (r != nullptr) {
        q->next = p;
        p = q;
        q = r;
        r = r->next;
    }
    q->next = p;
    head->next = q;
}

时间复杂度为 O(n)，空间复杂度为 O(1)。

相关问题

用STL List容器编写矩阵就地转置

下面是使用STL List容器实现矩阵就地转置的代码：

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

// 矩阵就地转置函数
void transpose(list<list<int>>& matrix) {
    // 获取矩阵的行数和列数
    int rows = matrix.size();
    int cols = matrix.front().size();

    // 对角线以下的元素与对角线以上的元素交换位置
    for (int i = 0; i < rows; i++) {
        auto it_i = matrix.begin();
        advance(it_i, i);
        auto it_j = it_i;
        advance(it_j, i + 1);
        for (int j = i + 1; j < cols; j++) {
            swap(*(*it_i).begin(), *(*it_j).begin());
            advance(it_i, 1);
            advance(it_j, 1);
        }
    }

    // 每一行逆序
    for (auto& row : matrix) {
        row.reverse();
    }
}

// 打印矩阵函数
void print_matrix(const list<list<int>>& matrix) {
    for (const auto& row : matrix) {
        for (const auto& elem : row) {
            cout << elem << " ";
        }
        cout << endl;
    }
}

int main() {
    // 初始化矩阵
    list<list<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    // 打印原始矩阵
    cout << "Original matrix:" << endl;
    print_matrix(matrix);

    // 就地转置矩阵
    transpose(matrix);

    // 打印转置后的矩阵
    cout << "Transposed matrix:" << endl;
    print_matrix(matrix);

    return 0;
}

这里使用了两个STL List的成员函数：`begin()`和`advance()`。`begin()`函数返回一个迭代器指向容器中第一个元素，而`advance()`函数可以将迭代器按照指定的步长移动。这些函数都是STL中的通用函数，可以用于操作各种STL容器。

用STL编写矩阵就地转置

可以使用STL中的vector来表示矩阵，然后再对其进行就地转置。以下是示例代码：

#include <iostream>
#include <vector>

using namespace std;

void transpose(vector<vector<int>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < m; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}

int main() {
    vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    cout << "Original matrix:" << endl;
    for(auto row: matrix) {
        for(auto val: row) {
            cout << val << " ";
        }
        cout << endl;
    }
    transpose(matrix);
    cout << "Transposed matrix:" << endl;
    for(auto row: matrix) {
        for(auto val: row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

运行结果：

Original matrix:
1 2 3 
4 5 6 
7 8 9 
Transposed matrix:
1 4 7 
2 5 8 
3 6 9