1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 24 题] “反转链表”做题记录

[剑指 Offer 第 2 版第 24 题] “反转链表”做题记录

第 24 题:输入一个链表,反转链表后,输出链表的所有元素

传送门:AcWing:反转链表牛客网 online judge 地址

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

样例:

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

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

分析:这道题同 LeetCode 上一道问题,可以使用“穿针引线”也可以使用递归求解。个人觉得递归的方式比较简单,但是在链表较长的时候,递归效率偏低,因为要使用系统栈。

思路1:递归。

Python 代码:

  # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    # 递归写法:用递归就不用思考穿针引线这种事情了。


    class Solution:
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            # 递归的终止条件一定要写对:考虑结点为空和单结点的情况
            if head is None or head.next is None:
                return head
            next = head.next
            new_head = self.reverseList(next)
            next.next = head
            head.next = None
            return new_head


Java 代码:

  class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class Solution {

        // 递归写法要画个图就清楚了
        public ListNode ReverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode next = head.next;
            ListNode newHead = ReverseList(next);
            next.next = head;
            head.next = null;
            return newHead;
        }

    }

思路2:非递归写法,穿针引线。

liwei201910118_1.png

Python 代码:

  # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    # 穿针引线,可以看到 while 循环体部分的代码是首尾相连的,有些单链表的题目也有这种规律,感觉很神奇
    # 在 Python 中,其实还有更简便的写法,就跟斐波拉契数列一样


    class Solution:
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """

            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
            return pre

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 24 题] “反转链表”做题记录

链接:https://www.javajike.com/article/3273.html

« [剑指 Offer 第 2 版第 23 题] “链表中环的入口结点”做题记录
[剑指 Offer 第 2 版第 25 题] “合并两个排序的链表”做题记录»

相关推荐

QR code