206.反转链表
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
思路
1.递归
递：将大问题分解为小问题，将整个链表依次拆解直到只剩下一个节点
归：在链表只剩下一个节点时开始”归“，使用head.next.next = head,head.next = None这两行代码从后往前（从原链表的视角看）将链表中的每一个连接改为反向的
2.迭代
假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
3.头插法
首先创建一个只有头节点的反转链表，从头到尾遍历原链表，将每次遍历到的节点按照头插法插入反转链表中，以此类推，当我们遍历完整个链表时就得到一个反转链表。
头插法：即每次都将将要插入的节点作为链表的首节点（不是头节点）
头插法代码实现：
node.next = head.next
head.next = node
代码
# Definition for singly-linked list.
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 not head:
# return head
#
# p = head
#
# reversed = ListNode()
# while p is not None:
# node = ListNode(p.val)
# node.next = reversed.next
# reversed.next = node
#
# p = p.next
#
# return reversed.next
prev = None
curr = head
while curr is not None:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
def reverseList1(self, head):
"""
递归法
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
new_head = self.reverseList1(head.next)
head.next.next = head
head.next = None
return new_head
def reverseList2(self, head):
"""
头插法
:type head: ListNode
:rtype: ListNode
"""
if not head:
return head
p = head
reversed = ListNode()
while p is not None:
node = ListNode(p.val)
node.next = reversed.next
reversed.next = node
p = p.next
return reversed.next
def create_linked_list(self, list):
"""根据list中的所有元素构建单链表"""
l = ListNode() # 单链表头节点
r = l # 起始尾指针r指向头节点
for e in list:
node = ListNode(e)
r.next = node
r = r.next
return l.next
def print_linked_list(self, linked_list) -> None:
"""
打印单链表中的所有元素
:param linked_list: 单链表
:return: 无
"""
print("----------------------------------------")
pointer = linked_list
while pointer is not None:
print(pointer.val)
pointer = pointer.next
if __name__ == "__main__":
slt = Solution()
linked_list = slt.create_linked_list([1, 2, 3, 4, 5])
slt.print_linked_list(linked_list)
reversed_linked_list = slt.reverseList1(linked_list)
slt.print_linked_list(reversed_linked_list)