高頻面試題： 單連結清單的反轉

高頻面試題： 單連結清單的反轉（個人筆記）

• input ： 1 -> 2 -> 3 -> 4 -> 5 -> None
• output : 5 -> 4 -> 3 -> 2 -> 1 -> None

python代碼思路：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 傳回ListNode
    def ReverseList(self, pHead):
        pre = None     # 定義傳回清單的頭指針
        cur = pHead   # 目前操作連結清單的操作節點指針
        while cur:      # 當cur不為空
            next = cur.next    # 将目前操作節點放到逆序清單首部前先标記好後面節點位置
            cur.next = pre    # 移動目前節點到逆序節點首部
            pre = cur    # 将逆序連結清單中的首指針指向新的首部節點
            cur = next   # 傳回cur指針到操作連結清單的首部
        return pre  # 傳回逆序清單的首部指針
           

大概如下圖示