每日一题-2

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解题思路

1.迭代
利用迭代的方法进行反转就需要几个辅助节点
newHead：设置一个新表头节点，表示反转链表的表头
p:这是一个辅助节点，主要作用是在head进行反转时，提前保存head.next，防止断链
利用迭代的方法，其实就是利用头插法，将原链表的元素插入到新链表里面，由于头插法插入的顺序刚好就是逆序的，这样即实现了链表的反转。在这个过程唯一需要注意的就是要设置一个辅助节点存储head.next，防止原链表断链，丢失后面的节点。

2.递归
递归的思想即是将原链表的反转分解为两步，第一步将head.next后面的节点进行反转，第二步将head与head.next进行反转。而第一步的反转又可以分别为相似的两步，以此为基础实现递归操作。
在这个过程中，需要主要的是，当链表走到了最后一个节点或原链表为空，它是没有下下个节点，所以只需要返回当前节点，这即是递归的结束条件。

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        #迭代
        # newHead = None
        # while(head):
        #     p = head.next
        #     head.next = newHead
        #     newHead = head
        #     head = p
        # return newHead
        #递归
        if((not head) or (not head.next)):
            return head
        newHead = self.reverseList(head.next)#先反转head后面的链表
        head.next.next = head#再反转head和head.next
        head.next = None
        return newHead