Reverse Linked List

题目

Reverse a singly linked list.

思路分析

这道题可以使用iterative和recursive两种方式来实现，用recursive的时候也可以通过自顶向下和自底向上两种方式来实现

首先用iterative来实现，基本思想是从linkedlist的head节点开始反转，先把head.next节点放到一个tmp节点中，然后将newHead assign给head.next，然后把head赋值给newHead，最后把tmp节点assign back给head节点

# 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 not head: return head
        if not head.next: return head
        node = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return node

接下来用recursive的方式来实现，首先用自底向上的方式：

自底向上的思想是先把节点一个一个压栈，一直到最后一个节点，这个时候开始向上进行linkedlist的反转，每一次返回的node都是linkedlist的最后一个节点，这个是不变的。所以在反转的时候一个容易出错的地方就是，对node的next进行操作

# 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 not head: return head
        if not head.next: return head
        node = self.reverseList(head.next)
        head.next.next = head   <<<< 这里会错误地写成node.next = head，为什么不能用node.next呢？是因为在自底向上的时候，node一直都是原始linkedlist的最后一个节点
        head.next = None
        return node

自顶向下的思想类似于iterative，从head开始反转，一边反转一边向下移动。这个实现方式要借助一个辅助函数，因为要使用到两个input，一个是当前节点，另外一个是previous节点

# 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 not head: return head
        return self.reverse(head, None)

    def reverse(self, node, prev):
        if not node: return prev
        tmp = node.next   <<<< 先把node.next节点放在tmp中
        node.next = prev  <<<< 然后对node.next进行反转，指向它的前面的那个节点
        newHead = self.reverse(tmp, node)    <<<< 自顶向下依次对每一个节点进行反转，直到最后一个节点
        return newHead