You should do val = val.next instead of val.next = val.next.next. The way you're doing it, the list will be truncated to a single element when you call count_length. Because you do count_length at the top of kth_to_last, by the time you get around to walking your list (where your 'hi' is), the list has already been reduced to a single node.

Remember, a linked list is a structure where each node's next property is a pointer to the next node. Your code is modifying the value of next, which is changing the structure of your linked list.

When you process a linked list (in count_length, or in kth_to_last), what you want to do is point yourself at each node in turn. You're not trying to modify the nodes themselves, so you won't assign to their value or next attributes. The way to do this is to change what your pointer (val) is pointing at, and the thing that you want it to point at next is the next node along. Therefore:

val = ll.head
while val is not None:
    # do something with val here
    val = val.next

You're doing way more work than you have to. Once you've implemented __iter__, the rest falls into place. You can use it to implement pretty much all your other functions, like get_node, __str__ or __repr__, etc.

class Node:

    def __init__(self, value):
        self.value = value
        self.next = None

    def __str__(self):
        return str(self.value)


class LinkedList:

    def __init__(self):
        self.head = None

    def add(self, value):
        if self.head is None:
            self.head = Node(value)
        else:
            for cursor in self:
                pass
            cursor.next = Node(value)
        return self

    def get_node(self, node_index):
        for index, node in enumerate(self):
            if index == node_index:
                break
        else:
            return None
        return node

    def __str__(self):
        return " -> ".join(map(str, self))

    def __iter__(self):
        cursor = self.head
        while cursor is not None:
            yield cursor
            cursor = cursor.next

ll = LinkedList().add(1).add(2).add(3)
print(ll)

for node_index in 0, 1, 2, 3:
    print("The node at index {} is {}".format(node_index, ll.get_node(node_index)))

Output:

1 -> 2 -> 3
The node at index 0 is 1
The node at index 1 is 2
The node at index 2 is 3
The node at index 3 is None
>>> 

why set curr.next to newNode and then completely overwrite it with curr = newNode?

These are two different type of assignment. The first -- assigning to curr.next -- mutates whatever object that curr is referencing. The second -- curr = newNode -- merely changes what curr references to. It doesn't mutate the data structure. It may help to visualise what happens. Let's say curr references a ListNode instance with value 1:

curr
  │
┌─┴──────────┐
│ val: 1     │
│ next: None │
└────────────┘

And newNode was just created with a value 2:

curr              newNode
  │                 │
┌─┴──────────┐    ┌─┴──────────┐
│ val: 1     │    │ val: 2     │
│ next: None │    │ next: None │
└────────────┘    └────────────┘

Then the first assignment -- curr.next = newNode will accomplish this:

curr              newNode
  │                 │
┌─┴──────────┐    ┌─┴──────────┐
│ val: 1     │    │ val: 2     │
│ next: ──────────┤ next: None │
└────────────┘    └────────────┘

And the second assignment, leads to this state:

                  curr newNode
                    │    │
┌────────────┐    ┌─┴────┴─────┐
│ val: 1     │    │ val: 2     │
│ next: ──────────┤ next: None │
└────────────┘    └────────────┘

The same would have happened, if the second assignment would have been curr = curr.next, since at that point curr.next and newNode reference the same object. This should also explain the rationale for your second point concerning l1 = l1.next. This merely traverses one step through a linked list with a variable. It doesn't affect that linked list itself.

How does returning dummyHead.next works? This value wasn't modified, it's just an empty list in the beginning.

The list was modified. But it happened via a different variable... curr. Note how initially curr references the same object as dummyHead, and then in the loop, the assignment to curr.next is setting the next attribute that dummyHead references, so that now dummyHead.next references a list with one element. And curr will move on to reference that element, and again set its next attribute, making that linked list having 2 nodes, ...etc

Your init function is incorrect.

Instead of

def __init__(self, initdata):
    self.data = initdata
    self.next_node = None

it should be

def __init__(self, initdata):
    self.data = initdata
    self.next= None

The dunder method for the next item is __next__ rather than __next, and you seem to be missing code that actually moves through the list as you iterate.

The normal method I use is to have a separate iterator class within the type to do the grunt work. In addition, the way you have your list set up makes the idea of an element class desirable as well (were you using a Python list, this would not be needed but, since you want an item and next "pointer", it's better as a separate class).

Let's start by creating the list class with an enclosed item class:

class MyList:
    # Single element in the list.

    class MyListElem:
        def __init__(self, item, link_from = None, link_to = None):
            # Set data, link from previous and to next if specified.

            self._item = item
            self._next = link_to
            if link_from is not None:
                link_from.change_link(self)

        def change_link(self, item):
            self._next = item

The element class has two methods, the first creating an element with links as needed. At the moment (see MyList.add() below), the to link is always None as we only append to the list.

Similarly, the from link is either None or the current tail, depending on whether we're adding the first or subsequent elements to the list.

These parameters are mostly here to cater for the possibility of later being able to insert at arbitrary places in the list.

Next is the iterator class, also part of the list class:

    # Iterator over the list.

    class MyListIter:
        def __init__(self, head):
            # Start at the head.

            self._curr = head

        def __iter__(self):
            # To iterate over the iterator rather than collection.

            return self

        def __next__(self):
            # Check more left, advance to next and return current.

            if self._curr is None:
                raise StopIteration
            ret_val = self._curr._item
            self._curr = self._curr._next
            return ret_val

This is relatively simple, the initialiser just sets us up so that the first call will return the head. The __iter__ call allows you to retrieve an iterator from the collection and then iterate over that, rather than iterating directly over the collection. The difference being:

for iter in object:         # iterate over object
    pass
iter = object.__iter__()    # iterate over iterator
for iter2 in iter:
    pass

See here for more details on why this may be necessary.

The __next__ call is the "meat" of the iterator. It raises an exception if the iterator is finished. Otherwise it returns the current value, after advancing to the next.

And then the list class itself, a very simple one that only allows appending to the end, no deleting, and an iterator to process it:

    # The list itself.

    def __init__(self):
        # Empty list to start with.

        self._head = None
        self._tail = None

    def add(self, val):
        # Append to the end of the list.

        if self._head is None:
            self._head = self.MyListElem(val)
            self._tail = self._head
        else:
            self._tail = self.MyListElem(val, self._tail)

    def __iter__(self):
        return self.MyListIter(self._head)

It's really that easy (well, relatively easy). The following test code shows it in action:

x = MyList()
x.add(12345)
x.add(42)
x.add("Hello")
x.add([1, 2, 3])
for i in x:
    print(i)

The output of that is, as expected:

12345
42
Hello
[1, 2, 3]

Confession: I've never actually written a linked list. At a cursory glance, this implementation looks fine, but I don't know any of the common mistakes. Would be good for somebody who knows more about them (perhaps even an actual interviewer) to give it the stamp of approval.

Working from top-to-bottom:

• There are no docstrings or comments anywhere in this code. I'm aware that's not always possible in an interview situation – but since you're writing this in advance, you can probably do it (after the fact, if nothing else).

  It makes the code easier to read, review and maintain. It's also a good way to expose code that doesn't really make sense.

• The __repr__ of a class is usually a string that could be eval’d to get an equivalent object. What you’ve written for Node is more like what I’d expect for __str__. More like:

  def __repr__(self):
      return '%s(data=%r, next_node=%r)' % (self.__class__.__name__,
                                            self.data,
                                            self.next)
  

• In the prepend method of LinkedList, you're not taking advantage of the constructor API you've defined for Node. You could write it more compactly as:

  def prepend(self, data):
      new_head = Node(data, next_node=self.head)
      self.head = new_head
  

  There's also a typo – the new_head2 variable isn't defined. Perhaps you meant self.head = new_head? In which case this becomes a one liner:

  def prepend(self, data):
      self.head = Node(data, next_node=self.head)
  

• In general, there's a lot of similar-looking code that strides back and forth through your linked lists. Lots of iter_nodes and positions and the like. Would be good to cut that down.

  Remembering that I know nothing about linked lists, I think it might be helpful to define a __len__ method on your LinkedList class. Combined with __getitem__, this could simplify your insert() and delete() methods.

  Something like:

  def insert(self, position, data):
      # This is incomplete -- you'll need to handle KeyErrors and
      # the like.  To mimic the insert() method on __builtin__.list,
      # if position > len(self), just stick it at the end.
      prev_node = self[position]
      next_node = self[position + 1]
      new_node = Node(data, next_node=next_node)
      prev_node.next = new_node
  

  This then drastically simplifies the code for prepend() and append():

  def prepend(self, data):
      self.insert(position=0, data=data)
  
  def append(self, data):
      # Probably want to check I haven't introduced an off-by-one
      # error here.
      self.insert(position=len(self), data=data)
  

• If nothing else, it seems like you could make more use of your __iter__ method, which comes right at the end and almost seems like an afterthought. That could be really useful. Some examples:

  def __eq__(self, other):  # other is the standard arg here
      if len(self) != len(other):
          return False
      for node_s, node_o in zip(self, other):
          if node_s != node_o:
              return False
      return True
  

• I would have your __getitem__ method raise an IndexError if I search off the end of the list, or before I've put in any data. This is a better fit with the semantics of the builtin list. And again, you can rewrite it to take advantage of __iter__:

  def __getitem__(self, position):
      if not self.head or len(self) < position:
          raise IndexError
      for idx, node in self:
          if idx == position:
              return node
  

  Note also that I'm returning the Node instance, not just the data from that node.

• Include an example. Again, caveat that I haven't done this sort of interview much, so don't know if this is even possible, but a little snippet showing how this list is supposed to be used would be helpful.

  It shows off the API, how you think the class should be used, and it's a good way to spot blatantly silly interfaces.

  It also helps if there's a bug in your code – such as the next_head2 typo – because I can see where you were aiming.

And a few quick nitpicks:

• Don't put spaces around default arguments, for example in the __init__ for your Node object.

• Single line between methods on the same class, for example in LinkedList.

• Compare to None with if foo is [not] None, for example in the append method of LinkedList.

I noticed that if I use while fast.next instead of while fast and fast.next for the loop, I got the same results.

This will work for input lists that have an odd number of nodes, but it will fail withe input lists that have an even number of nodes -- the trivial example being an empty list (with 0 nodes).

May I ask why I should use both fast and fast.next to stop the while loop?

In each iteration a pair of nodes is traversed, so in the case of an even number of nodes, there will come a situation where fast is None at the moment the while condition is evaluated. If you then only check fast.next -- without first ensuring that fast is really a node -- it will raise an error, as this really means you're doing None.next which of course doesn't work.

From my understanding, if fast.next is None, fast is always none, is this correct?

No, this is not correct. If fast.next is None then this implies that fast is a node with a next attribute, so certainly fast is then not None. But fast.next can produce an error when fast is None. It is for that reason that before evaluating fast.next one must be sure that fast is a node and not None.

If the condition is fast and fast.next and it happens that fast is None then the evaluation will short-circuit and fast.next will not be evaluated at all (and that's what you want to avoid an error). This is because the and operation is already sure to evaluate to a falsy value when the left-side operand (fast) has been evaluated to be None.

Just as mentioned by @abarnert , you always need a __iter__ method for the iterator class.

class LinkedListIterator:
    def __init__(self, head):
        self.current = head

    def __iter__(self):
        return self

    def __next__(self):
        if not self.current:
            raise StopIteration
        else:
            item = self.current.get_data()
            self.current = self.current.get_next()
            return item

class LinkedList:
    def __init__(self):
        self.head = None

    def __iter__(self):
        return LinkedListIterator(self.head)

    def add(self, item): 
        new_node = Node(item)
        new_node.set_next(self.head)
        self.head = new_node

Now that your class is iterable, you can use "for...in" loop:

test_list = LinkedList()
test_list.add(1)
test_list.add(2)
test_list.add(3)
for item in test_list:
    print(item)

Please check the tutorial here.

The del current node and return node_A.value, node_B.value, node_C.value commands should belong to the pop() function, so they should be indented. But anyway the del current node doesn't work for me. Instead you could write current_node.value = None but then you still return all 3 node values so the result would be 1,2,None.

I would rather write the pop() function inside the class and add another printlist() function to the class as well. The pop() function just removes the last element from the list (changes the next attribute to None for the 2nd last element in the list) and doesn't print or return anything. The printlist() function iterates through the list and prints out all elements (while there are next elements). Here is my code:

class LinkedList:
    def __init__(self, value):
        self.value = value
        self.next = None

    def pop(self):
        current_node = self
        while current_node.next:
            if current_node.next.next == None:
                current_node.next = None
            else:
                current_node = current_node.next

    def printlist(self):
        current_node = self
        lst = [current_node.value]
        while current_node.next:
            current_node = current_node.next
            lst.append(current_node.value)
        print lst


node_A = LinkedList(1)
node_B = LinkedList(2)
node_C = LinkedList(3)

node_A.next = node_B
node_B.next = node_C

try:
    node_A.pop()
    node_A.printlist()
except NameError:
    pass

If I run this, the result is [1,2]. If I remove the node_A.pop() I get [1,2,3]. If I write another node_A.pop() then result is [1].

For some needs, a deque may also be useful. You can add and remove items on both ends of a deque at O(1) cost.

from collections import deque
d = deque([1,2,3,4])

print d
for x in d:
    print x
print d.pop(), d

Since you just print the top value, None is always returned by your top function. Change it to return the top value instead of printing it:

    def top(self):
        if self.isEmpty() is  True:
            print("Hey! The stack is Empty")
            return
        else:
            return self.__head.data

Docstrings

A docstring for a class or function needs to be the first statement in the body of the class/function (see PEP 257). Thus, it should look as follows:

class MyClass:
    """
    This is a very useful class. 
    """

    def my_function(self):
        """
        This is a function. 
        """
        return None

This is used by the Python help system. For example, if you execute help(MyClass) you will get:

 Help on class MyClass in module __main__:
 
 class MyClass(builtins.object)
  |  This is a very useful class.
  |  
  |  Methods defined here:
  |  
  |  my_function(self)
  |      This is a function.

Instead, in your code comments are entered before definitions of classes and functions.

Docstrings for __init__(), __repr__() and __str__() are usually not needed, since these methods have standard functionality.

Arguments of __init__() should be described in the docstring for the class e.g.:

class Node:
    """    
    Node of a single linked list. 
    
    Parameters
    ----------
    value : Value of the node.
    next_node : Next node.
    """

    def __init__(self, value=None, next_node=None):
        self.value = value
        self.next = next_node

Then, executing help(Node) gives:

Help on class Node in module __main__:

class Node(builtins.object)
 |  Node(value=None, next_node=None)
 |  
 |  Node of a single linked list. 
 |  
 |  Parameters
 |  ----------
 |  value : Value of the node.
 |  next_node : Next node.
 | …

Notice that Python automatically uses __init__ to show how to construct a class instance and what the default values of the constructor arguments are.

By the way, in the __init__ method I replaced the argument next with next_node. next is a name of a built-in Python function, and variable names in your code should not clash with it.

String representations

The return value of __repr__() is supposed be a string representation of the object. To the extent possible, it should look like a valid Python code which, if it was executed, would produce the represented object. For example, in the Node class I would define __repr__() as follows:

def __repr__(self):
    if self.next is None:
        repr_next = repr(None)
    else:
        repr_next = super(Node, self.next).__repr__()
    return f"Node(value={repr(self.value)}, next_node={repr_next})"

Then executing

node1 = Node(4)
repr(node1)

one gets:

'Node(value=4, next_node=None)'

The code

node2 = Node(10, next_node=node1)
repr(node2)

gives:

'Node(value=10, next_node=<__main__.Node object at 0x1194813d0>)'

In this case we can’t return code that would link node2 to node1, but we can at least include a string describing the next node of node2.

The rules for the return value of __str__() are more flexible. It is supposed to be a user-friendly representation of the object. Still, in the Node class returning str(self.value) is misleading, since a Node instance is not the same thing as its value. If a user of your code who executes print(node1) sees 4, they may get an impression that they are dealing with an integer-like object and that something like 5 * node1 + 2 should work. I would use instead something like this:

def __str__(self):
    return f"[{str(self.value)}] -> {str(None) if self.next is None else  '...'}"

Then print(node1) gives

[4] -> None

and print(node2) yields

[10] -> ...

The three dots are intended to convey the information that the node is followed by another node. This is not the only (and possibly not the best) option, but it gives a better representation of what a node is than the value of the node alone.

__repr__() and __str__() in the LinkedList class should be redefined to be compatible with string representations of Node objects. An additional issue in this case is, that a linked list may consist of many nodes, and if __repr__() and __str__() try to list all of them, the resulting strings can be huge. I would print, say, up to three nodes and somehow indicate if the list continues beyond that. For example:

def __str__(self):
    if self.head is None:
        return str(None)

    llist_str = ""
    N = 2
    for i, node in enumerate(self):
        if node.next is not None:
            s = str(node)[:-3]
        else:
            s = str(node)
        llist_str += s
        if i >= N:
            break
    if node.next is not None:
        llist_str += "..."
    return llist_str  

Then the code

llist = LinkedList(4)
llist.append(5)
llist.append(7)
llist.append(10)
print(list)

Gives:

[4] -> [5] -> [7] -> ...

Appending and deleting

It is rather inconvenient that the constructor of LinkedList allows one to create linked lists with precisely one node only. In particular, an empty list can be created only indirectly, using something like

llist = LinkedList(1).delete(1)

It is better to modify __init__ so it accepts an iterable as an argument, and creates a linked list using values produced by the iterable:

def __init__(self, values):
    self.head = None
    for v in values:
        self.append(v) 

Additionally, I would change the append() method as follows:

def append(self, value):
    if self.head is None: 
        self.head = Node(value)
    else:
        for current in self:
            pass
        current.next = Node(value)

In particular I would use if self.head is None instead of if not self.head as it is done in your code. It is more explicit. Also, it will work even if at some point you decide to implement __bool__() in the Node class to redefine what the boolean value of a node is. Both this version of append() and yours are not efficient, since they need to traverse the whole list in order to append a node. It would be better to keep track which node is the tail of the list, and use it to append new nodes.

prepend() can be simplified to

def prepend(self, value):
    self.head = Node(value, next=self.head)

Finally, I would probably rename the delete() method to remove(), since its functionality is analogous to remove() for Python lists: it removes the first node with the specified value.

You're a little bit limited by only having nodes and forward links, but it is possible to implement pop(-first) by making the first node subsume the second node:

class stack_linked(object):
    def __init__(self, data):
        self.data = data
        self.next = None

    def pop(self):
        data = self.data
        nxt = self.next
        if nxt is None:
            self.data = self.next = None
        else:
            self.data = nxt.data
            self.next = nxt.next
            nxt.next = None
        return data

Notes on LinkedList:

• The import is unused.
• It should allow creation of an empty list.
• Normally a linked list inserts items after the last item. Maybe I'm confused by the way insert works, but it looks like in your case head is always the last inserted entry in the list, and the list is traversed from head backwards through history using .next.
• delete should use search.

Notes on Stack:

• self.data should be self.entries or something else descriptive.
• prnt should be as_string or even __str__.
• int(val) does not check whether something is an integer, it just tries to convert a value to an integer.
• +, -, * and / are arithmetic, not binary, operators.
• In Python 3 mathematical operators are modeled as functions.
• is_integer, is_binary_operator and postfixEval should not be part of Stack - they are not fundamental to the stack in any way.

for the method my thought process is...

What method? get_position? insert? delete?

As @JacobIRR suggested, adding a way of printing your linked list can be helpful. Take a look:

class Element:

    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedList:

    def __init__(self):
        self.head = None

    def append(self, value):

        element = Element(value)

        if self.head is None:
            self.head = element
            return

        cursor = self.head
        while cursor.next is not None:
            cursor = cursor.next
        cursor.next = element

    def __str__(self):

        values = []

        cursor = self.head
        while cursor is not None:
            values.append(cursor.value)
            cursor = cursor.next
        return " -> ".join(values)


def main():

    linked_list = LinkedList()

    linked_list.append("Foo")
    linked_list.append("Bar")
    linked_list.append("Fizz")
    linked_list.append("Buzz")

    print(linked_list)

    return 0


if __name__ == "__main__":
    import sys
    sys.exit(main())

Output:

Foo -> Bar -> Fizz -> Buzz