[LeetCode][Python3] 206. Reverse Linked List

Problem :

https://leetcode.com/problems/reverse-linked-list/description/

My Solution :

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

def reverseList(self, head):

"""

:type head: ListNode

:rtype: ListNode

"""

if not head:

return

stack = []

curr = head

while curr:

stack.append(curr)

curr = curr.next

head = stack.pop()

curr = head

while stack:

curr.next = stack.pop()

curr = curr.next

curr.next = None

return head

Comment :

처음엔 위와 같이 stack을 활용하여 접근하였다. 하지만 두번 순회하기 때문에 조금 비 효율적이다. 따라서 아래와 같이 한번 순회로 끝낼 수 있도록 다시 풀었다.

My Solution2 :

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

def reverseList(self, head):

"""

:type head: ListNode

:rtype: ListNode

"""

before = None

curr = head

while curr:

tmp = curr.next

curr.next = before

before = curr

curr = tmp

return before