2020.12.6 原创

961-芦同学

发表文章数:61

首页 » LeetCode » 正文

206 反转链表

题目

反转一个单链表。

示例:

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

解答

解法一:利用外部空间

解法二:双指针迭代

我们可以申请两个指针,第一个指针叫 pre,最初是指向 null 的。
第二个指针 cur 指向 head,然后不断遍历 cur。
每次迭代到 cur,都将 cur 的 next 指向 pre,然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了),pre 就是最后一个节点了。

class Solution {
    public ListNode reverseList(ListNode head) {
        //申请节点,pre和 cur,pre指向null
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while(cur!=null) {
            //记录当前节点的下一个节点
            tmp = cur.next;
            //然后将当前节点指向pre
            cur.next = pre;
            //pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 申请两个节点,pre和 cur,pre指向None
        pre = None
        cur = head
        # 遍历链表,while循环里面的内容其实可以写成一行
        # 这里只做演示,就不搞那么骚气的写法了
        while cur:
            # 记录当前节点的下一个节点
            tmp = cur.next
            # 然后将当前节点指向pre
            cur.next = pre
            # pre和cur节点都前进一位
            pre = cur
            cur = tmp
        return pre   

接法三:递归解法

2020.12.6                    原创

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归终止条件是当前为空,或者下一个节点为空
        if(head==null || head.next==null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList(head.next);
        //这里请配合动画演示理解
        //如果链表是 1->2->3->4->5,那么此时的cur就是5
        //而head是4,head的下一个是5,下下一个是空
        //所以head.next.next 就是5->4(最关键的一句)
        head.next.next = head;
        //防止链表循环,需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur,也就是最后一个节点
        return cur;
    }
}

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 递归终止条件是当前为空,或者下一个节点为空
        if(head==None or head.next==None):
            return head
        # 这里的cur就是最后一个节点
        cur = self.reverseList(head.next)
        # 这里请配合动画演示理解
        # 如果链表是 1->2->3->4->5,那么此时的cur就是5
        # 而head是4,head的下一个是5,下下一个是空
        # 所以head.next.next 就是5->4
        head.next.next = head
        # 防止链表循环,需要将head.next设置为空
        head.next = None
        # 每层递归函数都返回cur,也就是最后一个节点
        return cur

未经允许不得转载:作者:961-芦同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《2020.12.6 原创》 发布于2020-12-12

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录