呓语Beta 2.0 首页 镜头后 灶台前 捐赠者名单 有趣的小站

leetcode 206 Reverse Linked List

文档信息

leetcode 206 Reverse Linked List

解法一 递归

# Definition for singly-linked list.
# 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
        """
        if head == None or head.next == None: # 有0个或1个元素的链表
            return head
        else:
            p = self.reverseList(head.next) # 获得新表头
            head.next.next = head # head.next是表尾 将head放在它后面,成为新表尾
            head.next = None # 将表尾next设置为None
            return p # 返回新表头

解法二 迭代

# Definition for singly-linked list.
# 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
        """
        prev = None # 初值是队尾
        curr = head 
        while curr != None:
            t = curr.next # 记录未处理指针
            curr.next = prev # 反向指向前一个元素
            prev = curr # 后移prev
            curr = t # 后移curr
        return prev # 返回新head

note

付费支持

由于本网站没有广告和任何形式的收入来源,希望获得您的资助。每篇技术性文章和每期shellcasts视频定价人民币1元,在您付费后可以任意观看和下载。

可以使用支付宝手机钱包扫描下方的二维码进行付款操作或者用支付宝转帐给richard.ma.19850509@gmail.com,谢谢!

Fork me on GitHub