单链表逆序的四种方法及Python代码实现

单链表逆序有以下几种方法： 1. 递归法 2. 迭代法（头插法） 3. 迭代法（尾插法） 4. 就地逆序（双指针法） 以下是各种方法的代码实现： 1. 递归法： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list_recursive(head): if not head or not head.next: return head new_head = reverse_list_recursive(head.next) head.next.next = head head.next = None return new_head ``` 2. 迭代法（头插法）： ```python def reverse_list_iterative_head_insertion(head): new_head = None while head: temp = head.next head.next = new_head new_head = head head = temp return new_head ``` 3. 迭代法（尾插法）： ```python def reverse_list_iterative_tail_insertion(head): new_head = None tail = None while head: temp = head.next if not new_head: new_head = head tail = head else: tail.next = head tail = head head = temp if tail: tail.next = None return new_head ``` 4. 就地逆序（双指针法）： ```python def reverse_list_in_place(head): if not head or not head.next: return head prev = None curr = head while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev ``` ######[AI写代码神器 | 475点数解答 | 2024-06-07 13:37:22]