Reverse Linked List – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem – Reverse Linked List – Leetcode Challenge – Python Solution.
Source – qiyuangong’s repository.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
# def reverseList(self, head):
# """
# :type head: ListNode
# :rtype: ListNode
# """
# # iteratively
# if head is None:
# return
# stack = []
# pos = start = head
# while pos is not None:
# stack.append(pos)
# pos = pos.next
# while len(stack) > 0:
# if len(stack) >= 2:
# stack[0].val, stack[-1].val = stack[-1].val, stack[0].val
# stack.pop(0)
# stack.pop()
# else:
# stack.pop()
# return head
#
# def reverseList(self, head):
# # recursively
# if head is None:
# return head
# stack = []
# pos = head
# while pos is not None:
# stack.append(pos)
# pos = pos.next
# pre_head = ListNode(-1)
# self.do_reverse(stack, pre_head)
# return pre_head.next
#
# def do_reverse(self, stack, curr_head):
# if len(stack) == 0:
# curr_head.next = None
# return
# node = stack.pop()
# curr_head.next = node
# curr_head = node
# self.do_reverse(stack, curr_head)
# def reverseList(self, head):
# # simple iteratively without extra space
# prev, curr = None, head
# while curr is not None:
# next_temp = curr.next
# curr.next = prev
# prev = curr
# curr = next_temp
# return prev
def reverseList(self, head):
# recursion
# simple recursively without extra space
if head is None or head.next is None:
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
