Skip to content

206 reverse linked list

206. Reverse Linked List

题目: https://leetcode.com/problems/reverse-linked-list/

难度: Easy

用三个指针,分别指向prev,cur 和 nxt,然后loop一圈还算比较简单.

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev = None 
        cur = head
        while(cur):
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

其实一个指针就够了

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        prev = None
        while head.next:
            tmp = head.next
            head.next = prev
            prev = head
            head = tmp
        head.next = prev  
        return head

递归版本,可以再消化一下.

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        return self.reverseHelper(head, None)

    def reverseHelper(self, head, new_head):
        if not head:
            return new_head
        nxt = head.next
        head.next = new_head
        return self.reverseHelper(nxt, head)


回到顶部