菜鸟笔记
提升您的技术认知

反转链表的4种方法c++实现

1 迭代反转

3个指针,beg,mid,end;如图所示:

3 个指针每次各向后移动一个节点,直至 mid 指向链表中最后一个节点(此时 end 为 NULL )。需要注意的是,这 3 个指针每移动之前,都需要做一步操作,即改变 mid 所指节点的指针域,另其指向和 beg 相同。

1) 在图 3 的基础上,我们先改变 mid 所指节点的指针域指向,另其和 beg 相同(即改为 NULL),然后再将 3 个指针整体各向后移动一个节点。整个过程如图 4 所示:

2) 在图 4 基础上,先改变 mid 所指节点的指针域指向,另其和 beg 相同(指向节点 1 ),再将 3 个指针整体各向后移动一个节点。整个过程如图 5 所示:

3) 在图 5 基础上,先改变 mid 所指节点的指针域指向,另其和 beg 相同(指向节点 2 ),再将 3 个指针整体各向后移动一个节点。整个过程如图 6 所示:

4) 图 6 中,虽然 mid 指向了原链表最后一个节点,但显然整个反转的操作还差一步,即需要最后修改一次 mid 所指节点的指针域指向,另其和 beg 相同(指向节点 3)。如图 7 所示:

注意,这里只需改变 mid 所指节点的指向即可,不用修改 3 个指针的指向

 5) 最后只需改变 head 头指针的指向,另其和 mid 同向,就实现了链表的反转

//迭代反转法,head 为无头节点链表的头指针
link* reverse(link* head)
{
    if(head ==NULL || head->next == NULL)
        return head;
    link* beg = NULL;
    link* mid = head;
    link* end = head->next;

    //遍历
    while(1)
    {
        //修改mid所指节点的指向beg
        mid->next = beg;
        //判断end是否最后了
        if(end == NULL)
            break;
        //调整向后移动
        beg = mid;
        mid = end;
        end = end->next;    
    }
    //修改head头指针的指向
    head = mid;
    return head;
}

2 头插

所谓头插法,是指在原有链表的基础上,依次将位于链表头部的节点摘下,然后采用从头部插入的方式生成一个新链表,则此链表即为原链表的反转版

link * reverse(link * head) {
    link * new_head = NULL;
    link * temp = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    while (head != NULL)
    {
        temp = head;
        //将 temp 从 head 中摘除
        head = head->next;
        //将 temp 插入到 new_head 的头部
        temp->next = new_head;
        new_head = temp;
    }
    return new_head;
}

3 就地逆转

就地逆置法和头插法的实现思想类似,唯一的区别在于,头插法是通过建立一个新链表实现的,而就地逆置法则是直接对原链表做修改,从而实现将原链表反转

值得一提的是,在原链表的基础上做修改,需要额外借助 2 个指针(假设分别为 beg 和 end)。仍以图 1 所示的链表为例,接下来用就地逆置法实现对该链表的反转:

link * reverse(link * head) {
    link * beg = NULL;
    link * end = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    beg = head;
    end = head->next;
    while (end != NULL) {
        //先将end节点的下一节点接上beg节点,将 end 从链表中摘除
        beg->next = end->next;
        //将 end 移动至链表头
        end->next = head;
        head = end;
        //调整 end 的指向,另其指向 beg 后的一个节点,为反转下一个节点做准备
        end = beg->next;
    }
    return head;
}

4 递归反转(限无头节点)

这里相当于每次压栈,进入一个节点,到最后节点的时候,开始出栈,并进行一个链表反转操作

link* reverse(link* head) {
    //递归的出口
    if (head == NULL || head->next == NULL)     // 空链或只有一个结点,直接返回头指针
    {
        return head;
    }
 
    else
    {
        //一直递归,找到链表中最后一个节点
        link *new_head = reverse(head->next);
 
        //当逐层退出时,new_head 的指向都不变,一直指向原链表中最后一个节点;
        //递归每退出一层,函数中 head 指针的指向都会发生改变,都指向上一个节点。
 
        //每退出一层,都需要改变 head->next 节点指针域的指向,同时令 head 所指节点的指针域为 NULL。
        head->next->next = head;
        head->next = NULL;
        //每一层递归结束,都要将新的头指针返回给上一层。由此,即可保证整个递归过程中,能够一直找得到新链表的表头。
        return new_head;
    }
}