【Leetcode】206—Reverse Linked Lis

一、题目描述

反转一个单链表。
示例：

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

二、代码实现

方法一、迭代法

# 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
        """
        pre = None
        cur = head
        while cur:
            last = cur.next
            cur.next = pre
            pre = cur
            cur = last
        
        return pre

方法二、递归法

先反转后面的链表，从最后面的两个结点开始反转，依次向前，将后一个链表结点指向前一个结点，注意每次反转要后要将原链表中前一个结点的指针置空，表示将原链表中前一个结点指向后一个节点的指向关系断开。

https://www.cnblogs.com/kubixuesheng/p/4394509.html

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

参考：https://blog.csdn.net/qq_17550379/article/details/80647926
https://www.cnblogs.com/kubixuesheng/p/4394509.html