LeetCode反转链表的方式有哪些

发布时间：2021-12-15 14:17:03 阅读：201 作者：小新栏目：大数据

开发者测试专用服务器限时活动，0元免费领，库存有限，领完即止！点击查看>>

这篇文章主要为大家展示了“LeetCode反转链表的方式有哪些”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“LeetCode反转链表的方式有哪些”这篇文章吧。

问题描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

使用栈解决

链表的反转是老生常谈的一个问题了，同时也是面试中常考的一道题。最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。原理如下

代码比较简单，来看下

 1public ListNode reverseList(ListNode head) { 2    Stack<ListNode> stack = new Stack<>(); 3    //把链表节点全部摘掉放到栈中 4    while (head != null) { 5        stack.push(head); 6        head = head.next; 7    } 8    if (stack.isEmpty()) 9        return null;10    ListNode node = stack.pop();11    ListNode dummy = node;12    //栈中的结点全部出栈，然后重新连成一个新的链表13    while (!stack.isEmpty()) {14        ListNode tempNode = stack.pop();15        node.next = tempNode;16        node = node.next;17    }18    //最后一个结点就是反转前的头结点，一定要让他的next19    //等于空，否则会构成环20    node.next = null;21    return dummy;22}

双链表求解

双链表求解是把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表。下面以链表1→2→3→4为例画个图来看下。

LeetCode反转链表的方式有哪些

他每次访问的原链表节点都会成为新链表的头结点，最后再来看下代码

 1public ListNode reverseList(ListNode head) { 2    //新链表 3    ListNode newHead = null; 4    while (head != null) { 5        //先保存访问的节点的下一个节点，保存起来 6        //留着下一步访问的 7        ListNode temp = head.next; 8        //每次访问的原链表节点都会成为新链表的头结点， 9        //其实就是把新链表挂到访问的原链表节点的10        //后面就行了11        head.next = newHead;12        //更新新链表13        newHead = head;14        //重新赋值，继续访问15        head = temp;16    }17    //返回新链表18    return newHead;19}

递归解决

我们再来回顾一下递归的模板，终止条件，递归调用，逻辑处理。

 1public ListNode reverseList(参数0) { 2    if (终止条件) 3        return; 4 5    逻辑处理（可能有，也可能没有，具体问题具体分析） 6 7    //递归调用 8    ListNode reverse = reverseList(参数1); 910    逻辑处理（可能有，也可能没有，具体问题具体分析）11}

终止条件就是链表为空，或者是链表没有尾结点的时候，直接返回

if (head == null || head.next == null)    return head;

递归调用是要从当前节点的下一个结点开始递归。逻辑处理这块是要把当前节点挂到递归之后的链表的末尾，看下代码

 1public ListNode reverseList(ListNode head) { 2    //终止条件 3    if (head == null || head.next == null) 4        return head; 5    //保存当前节点的下一个结点 6    ListNode next = head.next; 7    //从当前节点的下一个结点开始递归调用 8    ListNode reverse = reverseList(next); 9    //reverse是反转之后的链表，因为函数reverseList10    // 表示的是对链表的反转，所以反转完之后next肯定11    // 是链表reverse的尾结点，然后我们再把当前节点12    //head挂到next节点的后面就完成了链表的反转。13    next.next = head;14    //这里head相当于变成了尾结点，尾结点都是为空的，15    //否则会构成环16    head.next = null;17    return reverse;18}

因为递归调用之后head.next节点就会成为reverse节点的尾结点，我们可以直接让head.next.next = head;，这样代码会更简洁一些，看下代码

1public ListNode reverseList(ListNode head) {2    if (head == null || head.next == null)3        return head;4    ListNode reverse = reverseList(head.next);5    head.next.next = head;6    head.next = null;7    return reverse;8}

这种递归往下传递的时候基本上没有逻辑处理，当往回反弹的时候才开始处理，也就是从链表的尾端往前开始处理的。我们还可以再来改一下，在链表递归的时候从前往后处理，处理完之后直接返回递归的结果，这就是所谓的尾递归，这种运行效率要比上一种好很多

 1public ListNode reverseList(ListNode head) { 2    return reverseListInt(head, null); 3} 4 5private ListNode reverseListInt(ListNode head, ListNode newHead) { 6    if (head == null) 7        return newHead; 8    ListNode next = head.next; 9    head.next = newHead;10    return reverseListInt(next, head);11}

尾递归虽然也会不停的压栈，但由于最后返回的是递归函数的值，所以在返回的时候都会一次性出栈，不会一个个出栈这么慢。但如果我们再来改一下，像下面代码这样又会一个个出栈了

 1public ListNode reverseList(ListNode head) { 2    return reverseListInt(head, null); 3} 4 5private ListNode reverseListInt(ListNode head, ListNode newHead) { 6    if (head == null) 7        return newHead; 8    ListNode next = head.next; 9    head.next = newHead;10    ListNode node = reverseListInt(next, head);11    return node;12}

以上是“LeetCode反转链表的方式有哪些”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

向AI问一下细节

LeetCode反转链表的方式有哪些

猜你喜欢

最新资讯

相关推荐

开发者交流群：

相关标签