靈感來源?

- 保持更新，努力學習

- python腳本學習

反轉鏈表

解題思路

1. 迭代法：通過遍歷鏈表，逐個改變節點的指針方向。具體步驟如下：

   • 使用三個指針：prev（初始為None）、curr（初始為頭節點）、next_node（用于保存當前節點的下一個節點）。
   • 在遍歷過程中，先保存當前節點的下一個節點，然后將當前節點的指針指向前一個節點，最后更新prev和curr指針。
   • 重復上述步驟，直到遍歷完整個鏈表，此時prev指針即為新的頭節點。

2. 遞歸法：通過遞歸調用反轉后續節點，然后調整當前節點的指針方向。具體步驟如下：

   • 遞歸反轉當前節點的后續鏈表。
   • 將當前節點的下一個節點的指針指向當前節點。
   • 將當前節點的指針置為None，避免形成環。

     # Definition for singly-linked list.
     class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:# 迭代方法def reverseList(self, head: ListNode) -> ListNode:prev = Nonecurr = headwhile curr:next_node = curr.next  # 保存下一個節點curr.next = prev       # 反轉指針prev = curr            # 移動prev指針curr = next_node       # 移動curr指針return prev                # 返回新的頭節點# 遞歸方法def reverseListRecursive(self, head: ListNode) -> ListNode:if not head or not head.next:return head# 遞歸反轉后續節點new_head = self.reverseListRecursive(head.next)# 調整指針方向head.next.next = headhead.next = Nonereturn new_head# 輔助函數：將列表轉換為鏈表
     def list_to_linkedlist(lst):dummy = ListNode(0)current = dummyfor val in lst:current.next = ListNode(val)current = current.nextreturn dummy.next# 輔助函數：將鏈表轉換為列表
     def linkedlist_to_list(head):result = []current = headwhile current:result.append(current.val)current = current.nextreturn result# 示例用法
     if __name__ == "__main__":# 創建鏈表 1->2->3->4->5head = list_to_linkedlist([1, 2, 3, 4, 5])# 使用迭代方法反轉鏈表solution = Solution()reversed_head = solution.reverseList(head)print("迭代方法反轉后的鏈表:", linkedlist_to_list(reversed_head))# 重新創建鏈表 1->2->3->4->5head = list_to_linkedlist([1, 2, 3, 4, 5])# 使用遞歸方法反轉鏈表reversed_head_recursive = solution.reverseListRecursive(head)print("遞歸方法反轉后的鏈表:", linkedlist_to_list(reversed_head_recursive))    

逐行解釋

# 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:prev = None           # 初始化前一個節點為Nonecurr = head           # 初始化當前節點為頭節點while curr:           # 遍歷鏈表直到當前節點為空next_node = curr.next  # 保存當前節點的下一個節點curr.next = prev       # 將當前節點的指針指向前一個節點prev = curr            # 前一個節點向后移動curr = next_node       # 當前節點向后移動return prev                # 返回新的頭節點（原鏈表的尾節點）# 遞歸方法：通過遞歸反轉后續節點，再調整當前節點的指針def reverseListRecursive(self, head: ListNode) -> ListNode:if not head or not head.next:  # 遞歸終止條件：節點為空或為尾節點return head# 遞歸反轉后續節點，返回新的頭節點new_head = self.reverseListRecursive(head.next)# 調整指針方向：將當前節點的下一個節點的next指向當前節點head.next.next = head# 斷開當前節點的next指針，防止形成環head.next = Nonereturn new_head                # 返回新的頭節點# 輔助函數：將列表轉換為鏈表
def list_to_linkedlist(lst):dummy = ListNode(0)  # 創建虛擬頭節點current = dummy      # 當前節點指向虛擬頭節點for val in lst:      # 遍歷列表current.next = ListNode(val)  # 創建新節點并連接current = current.next        # 當前節點后移return dummy.next  # 返回虛擬頭節點的下一個節點，即真正的頭節點# 輔助函數：將鏈表轉換為列表
def linkedlist_to_list(head):result = []         # 初始化結果列表current = head      # 當前節點指向頭節點while current:      # 遍歷鏈表result.append(current.val)  # 將當前節點的值添加到列表current = current.next      # 當前節點后移return result                   # 返回結果列表# 示例用法
if __name__ == "__main__":# 創建鏈表 1->2->3->4->5head = list_to_linkedlist([1, 2, 3, 4, 5])# 使用迭代方法反轉鏈表solution = Solution()reversed_head = solution.reverseList(head)print("迭代方法反轉后的鏈表:", linkedlist_to_list(reversed_head))# 重新創建鏈表 1->2->3->4->5head = list_to_linkedlist([1, 2, 3, 4, 5])# 使用遞歸方法反轉鏈表reversed_head_recursive = solution.reverseListRecursive(head)print("遞歸方法反轉后的鏈表:", linkedlist_to_list(reversed_head_recursive))