Ad

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):
          self.data = data
          self.next = 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 = current.next
     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 current.next, 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 current.next.  Then store the next node as the current node. The order matters when assigning current.next and the new current.

No comments:

Post a Comment

Natural Language Processing NLP - Useful libraries, tools and code samples

Basic Concepts Stop words removal Stop words are words that may not carry valuable information In some cases stop words matter . For e...