CODEWITHSUNDEEP
python-3.xlinked-list
entire_world
entire_world

Reputation: 31

How to create a linked list with previous pointer?

This question is inspired by a leetcode question Flatten a Multilevel Doubly Linked List .

Node is defined as below:

class ListNode:
  def __init__(self, val, prev, next):
    self.val = val
    self.prev = prev
    self.next = next

My question is how to create a custom node that includes both the previous and next pointer without incurring a loop error.

For example if I want to create a node that is [1->2->3], below is my thinking process:

a=node(1,None,b)
b=node(2,a,c)
c=node(3,b,None)

However wouldn't this cause a loop error, as a is defined by b, and b is in return defined by a, similarly for c, b is used to define c and at the same time c is used to define b. How can we find the value of something if its input is dependent on its output?

I am a bit confused right now, appreciate if you shed some light on this. Thank you

Upvotes: 0

Views: 197

Answers (1)

Konrad Rudolph
Konrad Rudolph

Reputation: 545598

You need to create the first node without links, and then amend the link later, when adding adjacent nodes.

For instance, I’d change Node to something like this:

class ListNode:
  def __init__(self, val, prev=None, next=None):
    self.val = val
    self.prev = prev
    if prev is not None:
      prev.next = self
    self.next = next
    if next is not None:
      next.prev = self

And then use it like this:

a = ListNode(1)
b = ListNode(2, a)
c = ListNode(3, b)

Upvotes: 1

Related Questions