反转链表

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

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

思路

定义三个节点，第一个节点和第二个节点负责连接链表，第三个链表负责连接前面两个链表和后一个链表。确定一个终止条件，这个终止条件我确定的不好。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        pre = None
        cur = head
        later = cur.next
        while cur:
            #指向
            cur.next=pre
            #更新
            pre=cur
            cur=later
            later=later.next if later is not None else later
        return pre

思路

使用递归的方式，交换两个链表依次递归下去

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverse(head, None)
    def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:
        if cur == None:
            return pre
        temp = cur.next
        cur.next = pre
        return self.reverse(temp, cur)

思路

使用栈存储节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return
        stack=[]
        while head:
            stack.append(head)
            head=head.next
        nullhead=ListNode()
        head=stack.pop()
        nullhead.next=head
        while stack:
            head.next=stack.pop()
            head=head.next
        head.next=None
        return nullhead.next

思路

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummp=None
        pre=dummp
        if not head:
            return None
        later=head.next
        while head:
            head.next=pre
            pre=head
            head=later
            later=later.next if later else None
        return pre

这个是最新写的，如果while遍历的时候选择later节点，会更好。