C++实现反转链表的两种方法

时间:2023-03-20 努力进大厂的新青年人气:0

大家好，今天和大家分享的是反转链表的两种方法，第一种是用泛型编程里面的STL，第二种是利用多个指针进行操作，小孩子才做选择，建议两个都学。我们往下看：

一.使用vector容器

ps：该方法对内存的需求较高，这是个缺点，可以直接使用STL容器自带的reverse进行反转(将vector容器内的结点进行反转，然后再用for循环将他串联起来)，实现起来相对容易，思路不太复杂。

请看以下代码：

typedef struct Node
{
 int val;
  struct Node*next;
 
}ListNode;
 
class traverse {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (!pHead) return nullptr;
        vector<ListNode*> v;
        while (pHead) {
            v.push_back(pHead);
            pHead = pHead->next;
        }
        reverse(v.begin(), v.end()); // 反转vector，也可以逆向遍历
        ListNode *head = v[0];
        ListNode *cur = head;
        for (int i=1; i<v.size(); ++i) { // 构造链表
            cur->next = v[i]; // 当前节点的下一个指针指向下一个节点
            cur = cur->next; // 当前节点后移
        }
        cur->next = nullptr; // 切记最后一个节点的下一个指针指向nullptr
        return head;
    }
};

此方法的复杂度：

时间复杂度：O(n)

空间复杂度：O(n), 用了一个vector来存单链表

二.调整指针法

ps：此方法更加妥当，能得到更多人的青睐，很好的利用几个指针的指向反转一个链表。

初始化：3个指针

1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr

2）cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head

3）nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存

接下来，循环执行以下三个操作

1）nex = cur->next, 保存作用

2）cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点

3）pre = cur， cur = nex; 指针后移，操作下一个未反转链表的第一个节点

循环条件，当然是cur != nullptr

循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点

这里以1->2->3->4->5 举例：

代码如下：

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = nullptr;
        ListNode *cur = pHead;
        ListNode *nex = nullptr; // 这里可以指向nullptr，循环里面要重新指向
        while (cur) {
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
    }
};

此方法复杂度：

时间复杂度：O(n), 遍历一次链表

空间复杂度：O(1)

总结：要从易懂的角度来看，第一种不失是好的，使用STL，我现在才大一，我听说一些面试是不允许使用STL这一内容解体的。第二种方法很妙，复杂度是比较理想的，而且用到了灵魂指针的应用。建议大家多琢磨一下第二种方法。

加载全部内容