ほぼ日刊競プロ leetcode　206. Reverse Linked List

206. Reverse Linked List

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

example1

考えたこと

自力では無理でした．．．

参考にしたサイト

# 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 None
       stack = []
       while head.next:
           stack.append(head)
           head = head.next
       print (head)
       while stack:
           cur = stack.pop()
           #print ("cur ="+str(cur))
           print ("cur next="+str(cur.next))
           #print ("cur next next="+str(cur.next.next))
           cur.next.next = cur
           #print (cur.next.next.val)
           #print ("cur next="+str(cur.next))
           cur.next = None
           
           
       return head
       

stackを用いる．
[1,2,3,4,5]の場合
while stack:の処理は以下のようになる
curには４，３，２，１で値が取り出されていて
4を取り出す時，cur.next.val=5
cur.next.next = curで5のポインタが4になる
つまり5->4
cur.next = Noneで5->4->Nullにしている
次のループで3を取り出し
元々3->4で繋がってたからcur.next.val=4
cur.next.next = curで４のポインタを3にする
5->4->3にし
cur.next = Noneで5->4->3->Null
で最後までやると5->4->3->2->1->Null
になる

難しい．．．