[数据结构与算法]LeetCode 206. 反转链表

1、题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

2、解答

解答链表的题目最好是好好画一下。理解题目描述的场景。

输入链表：
1-》2-》3-》4-》5

期待的输出是：5-》4-》3-》2-》1

开始遍历链表：

当前节点cur是1，他的next是2，那反转的意思是，将1的next指向None，

然后移动当前节点到2，2的next是3，反转就是把2的next指向之前的1。

这样梳理一下其实我们需要保存三个遍历：

prev:之前的节点

cur：当前遍历的节点

next：下一个待遍历的节点。

然后翻转就是先把cur.next = prev,最后移动prev,cur,next.
prev = cur, cur=next, next = next.next

• 迭代法：其实就是上面思路一直遍历到链表结束就行。
• 递归法：递归法需要反向思考一下，从最后输出的结果来考虑。最后结果的起点是从5开始，那么cur是5的时候，next是None，然后prev是4，那么需要的是cur.next = prev, 然后需要把prev.next = None，因为其实这个时候pre.next=cur,避免循环引用必须将prev.next修改。然后递归栈向上，cur变成了4， prev=3。

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


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

    def reverseList2(self, head):
        """
        递归法
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        p = self.reverseList2(head.next)
        # 下面这行代码是关键，它实现的就是链表反转
        head.next.next = head
        head.next = None
        return p

if __name__ == '__main__':
    head = [1, 2, 3, 4, 5]
    prev = None
    first = None
    for i in head:
        node = ListNode(i, None)
        if prev is not None:
            prev.next = node
        if prev is None:
            first = node
        prev = node

    sol = Solution()
    res = sol.reverseList2(first)
    print()