5/23 每日一題(反轉鍊表-單向)

 Given the head of a singly linked list, reverse the list, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

# 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]:

        #ex head=[1,2,3,4,5]

        newlink = None 

        cur = head #1>2>3>4>5>None

        

        while cur:

            next_node=cur.next 

            cur.next = newlink 

            newlink= cur 

            cur = next_node

            

        return newlink

"""

p.s 不能用 newlink = ListNode(Node) ,這樣變成創造新的鍊表,內有None節點,回傳時會多一個None

-----------------------------------------

第一次迴圈 , cur=1 

next_node=cur.next

#將原有順序存入next_node

#原本是 1->2->3->4->5->None

#新的是 1->None

cur.next=newlink

#cur=1恰好是反轉後的標頭

newlink=cur

#繼續走訪元素

cur=next_node

--------------------------------------------------------------

第二次迴圈 , cur=2

next_node=cur.next 

#將原有順序存入next_node

#原本是 2->3->4->5->None

#新的是 2->1->None

#所以關鍵在改變cur.next

cur.next = newlink

#更新標頭

newlink=cur

#繼續走訪

cur=next_node

-----------------------------------------------------

第三次迴圈, cur = 3

next_node = cur.next

#存入原有順序到next_node中

#目前的下一位是 3->4->5

#我們要的是 3->2->1->None

cur.next=newlink

#更新標頭

newlink=cur

#繼續走訪

cur=next_node

-------------------------------------------------

第四次迴圈, cur = 4

next_node = cur.next

#將原有順序存入next_node中

#原本為4->5

#新的是 4->3->2->1->None

cur.next=newlink

#更新標頭

newlink = cur

#繼續走訪

cur = next_node

------------------------------------------------

第五次迴圈, cur=5

next_node=cur.next

#將原有順序存入next_node中

#原本是 5->None 

#新的是 5->4->3->2->1->None

cur.next=newlink

#更新標頭

newlink=cur

cur=next_node

#cur變成None ,迴圈結束, 返回newlink 即為反轉後的鍊表

"""