Leetcode 206. Reverse Linked List 链表翻转 Python 两种解法

大鹅

发布于 2021-06-15 15:54:43

5690

发布于 2021-06-15 15:54:43

文章被收录于专栏：大鹅专栏：大数据到机器学习

问题描述

Reverse a singly linked list. 翻转一个链表

#1

第一种方法：迭代

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = cur = None
        if head:
            pre = head
            cur = head.next
            pre.next = None
        else:
            return None
        while cur:
            p = cur
            cur = cur.next
            p.next = pre
            pre = p
        return pre

#2

第二种方法：递归

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def reverseList(self, head):
        return reverse(head)

    def reverse(self, node, prev=None):
        if not node:
            return prev
        n = node.next
        node.next = prev
        return reverse(n, node)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018/03/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

list