链表逆置的四种方法详解

链表逆置的四种方法详解

引用

CSDN

1.

https://m.blog.csdn.net/2402_88002942/article/details/142885810

背景要求

给定一条链表，将其逆置。

方法一（循环迭代）

实现思路

设pre、cur、nxt三个指针，分别令其指向空、表头和q的下一个元素，如图：

令cur的next结点指向pre，如图：

令pre、cur、nxt依次向后移动，如图：

重复以上步骤，如下图：

至此，链表逆置成功。

实现代码

Node* reverse(Node* head) {
    Node* pre = NULL;
    Node* cur = head;
    Node* nxt = NULL;
    while (cur != NULL) {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    head = pre;
    return head;
}

复杂度

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

方法二（递归）

实现思路

递归
首先考虑出口，即递归至最深：head->next == NULL
借助栈理解即先将各个结点从头到尾压入栈，如图
到出口了，退栈：
逆置结束。
但说实话递归这件事在我这不能细想，一想就绕进去了，所以代码实现可以粗暴理解为：

实现代码

Node* Recursion_reverse(Node* head) {
    if (head == NULL || head->next == NULL) {//判空和出口
        return head;
    }
    else {
        Node* new_head = Recursion_reverse(head->next);
        head->next->next = head;
        head->next = NULL;
        return new_head;
    }
}

复杂度

时间复杂度O(n)，空间复杂度O(n)

方法三（头插法）

实现思路

跟打麻将摸牌一样，一张一张插进去就好，如图：

实现代码

Node* head_reverse(Node* head)
{
    Node* new_head = NULL;
    Node* temp = NULL;
    if (head == NULL || head->next == NULL)
        return head;
    while (head != NULL)
    {
        temp = head;
        head = head->next;
        temp->next = new_head;
        new_head = temp;
    }
    return new_head;
}

复杂度

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

方法四（就地逆置）

实现思路

其实就是这个
展开来讲，如下：
一条一条拧，就逆置过来了。

实现代码

Node* local_reverse(Node* head)
{
    Node* begin = NULL;
    Node* end = NULL;
    if (head == NULL || head->next == NULL)
        return head;
    begin = head;
    end = head->next;
    while (end != NULL)
    {
        begin->next = end->next;
        end->next = head;
        head = end;
        end = begin->next;
    }
    return head;
}

复杂度

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