Wednesday, December 13, 2017

Reverse a Linked List in Python - Technical Interviews Programming Interview

Take a moment to think about what would the data structure of a linked list look like in Python.

class Node:
     def __init__(data):
 = data
 = None

Each element of the Linked List is a node which contains data and a next pointer.

We use pointer to indicate a Python variable, which is not the same as the * operator.

To reverse a Linked List, you have to recursively put the current head as the previous node, the list head will become the second to last element and points to None, while the list tail is now the new head.

It's assume that the Linked List has a head pointer just like all Linked Lists defined by its abstract data structure (ADS)

current = head
prev = None
next = None

while current:
     next = = prev
     prev = current
     current = next
return prev

It gets a bit confusing in the middle. It's important to remember that the previous pointer starts with None, because the old head points to None after being reversed. Next serves as a temp pointer, we need to temporarily store, and change it to previous. Since we just completed processing the current node, we store it in the new prev variable, which has the current and new  Then store the next node as the current node. The order matters when assigning and the new current.

No comments:

Post a Comment

Reinforcement Learning Q Learning

Explore <s, a> ---> s' reads: move from current state s to s' via action a.   Through the action a reward  is received, it ...