欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【剑指Offer】反转链表

程序员文章站 2022-06-30 20:43:33
题目描述 输入一个链表,反转链表后,输出新链表的表头。 解法1 可以使用三个辅助指针pHead, last,next pHead记录当前节点,last记录上一个节点,next记录下一个节点 首先使用next保存当前节点的下一个节点,然后将当前节点的下一个节点指向last,实现反转 如下图所示 实现代 ......

题目描述

输入一个链表,反转链表后,输出新链表的表头。

解法1

可以使用三个辅助指针phead, last,next
phead记录当前节点,last记录上一个节点,next记录下一个节点
首先使用next保存当前节点的下一个节点,然后将当前节点的下一个节点指向last,实现反转
如下图所示
【剑指Offer】反转链表

实现代码

public listnode reverselist(listnode phead)
{
    listnode last = null, next = null;
    while(phead != null){
        next = phead.next;
        phead.next = last;
        last = phead;
        phead = next;
    }
    return last;
}

解法2

解法1是将链表按照从头到尾的顺序反转的
可以使用递归,通过不断递归深入,实现先从链表的尾节点开始反转
然后通过递归的回溯实现按照从尾到头的顺序反转每个节点
如下图所示
【剑指Offer】反转链表

实现代码

public listnode reverselist2(listnode phead)
{
    if(phead == null || phead.next == null) return phead;
    listnode node = reverselist2(phead.next);
    phead.next.next = phead;
    phead.next = null;
    return node;
}

更多算法题目的完整描述,ac代码,以及解题思路可以查看github仓库algorithm