# Writing an algorithm to shift a linked list according to `k` variance

Write a function that takes in the head of a Singly Linked List and an integer k, shifts the list in place (i.e., doesn’t create a brand new list) by k positions, and returns its new head.
Shifting a Linked List means moving its nodes forward or backward and wrapping them around the list where appropriate. For example, shifting a Linked List forward by one position would make its tail become the new head of the linked list.
Whether nodes are moved forward or backward is determined by whether k is positive or negative.
Each `LinkedList` node has an integer `value` as well as a `next` node pointing to the next node in the list or to `None` / `null` if it’s the tail of the list.
You can assume that the input Linked List will always have at least one node; in other words, the head will never be `None` / `null`.
Sample Input:

``````head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 # head node has value of 0
k = 2
``````

Sample Output:

``````4 -> 5 --> 0 -> 1 -> 2 -> 3 # the new head node with value of 4
``````

I already have written both Singly Linked List and Doubly Linked List algorithms with all kinds of methods for popping/appending/getting/inserting/removing. As you can read in the exercise above, it specifically says to complete the task with a “Singly Linked List” but I plan on writing 2 solutions - - one for Singly and one for Doubly. When I first read the challenge, I gravitated towards Doubly first because I encountered a gestalt and the solution for that seems more obivious. Once I have a solution for the Doubly Linked List version, I will return to Singly.

I made three attempts at shifting my DLL and my Python interpreter didn’t like any of them. All three attempts can be found below. Here is my absolute best effort:

``````def shift_linked_list(DLL_obj,k):
# if k > 0:
for iteration in range(0,k):
DLL_obj.cust_insert(0, DLL_obj.tail)
DLL_obj.cust_remove(DLL_obj.tail)
return DLL_obj

shift_linked_list(DLL_obj,2)
``````

Here is the traceback:

``````Traceback (most recent call last):
File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script10.py", line 207, in <module>
shift_linked_list(DLL_obj,2)
File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script10.py", line 204, in shift_linked_list
DLL_obj.cust_remove(DLL_obj.tail)
File "/home/gnull/dev/projects/python/2018-and-2020/algos/Doubly-Linked-Lists/script10.py", line 153, in cust_remove
if item_location < 0: # or item_location > self.length:
^^^^^^^^^^^^^^^^^
TypeError: '<' not supported between instances of 'Node' and 'int'
``````

It’s pointing to my Doubly Linked List `custom remove` method. You can find my full script and complete DLL algorithm below, including line 153 which is expecting the item_position. In my case I am passing in `DLL_obj.tail` which is not the position but the value of what is at that position. Right? To get the item_position, I figure I might need to use the Python builtin `len()` method but that only works on lists and my DLL isn’t a list. This means I can’t use the len() method in this context. My question for all of you: How do I grab the last item position of my DLL? If I can properly do that, I figure I should be able to use it to pass into my `cust_remove()` method and proceed with shifting a linked list according to `k` variance.

Here is my full DLL script:

``````class Node:
# Create a new node with the value passed to the function
def __init__(self, value):
self.value = value
self.next = None
self.prev = None

class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0

def add_right(self, value):
# If the head property is null set the head and tail to be the newly created node
newNode = Node(value)
if self.length == 0:
self.head = newNode
self.tail = newNode
# If not...
else:
# Set the next property on the tail to be that node
self.tail.next = newNode
# Set the previous property on the newly created node to be the tail
newNode.prev = self.tail
# Set the tail to be the newly created node
self.tail = newNode
# Increment the length
self.length = self.length + 1
# Return the Doubly Linked List
return self

def pop_right(self):
# If there is no head, return undefined
if self.head == None:
return "Undefined"
else:
# Store the current tail in a variable to return later
temp = self.tail
# If the length is 1, set the head and tail to be null
if self.length == 1:
self.head == None
self.tail == None
# Update the tail to be the previous Node
self.tail = self.tail.prev
# Set the newTail's next to null
self.tail.next = None
# Decrement the length
self.length = self.length - 1
# Return the value removed
return temp

def add_left(self, value):
# If the head property is null set the head and tail to be the newly created node
newNode = Node(value) # If the length is 0
if self.length == 0:
self.head = newNode # Set the head to be the new node
self.tail = newNode # Set the tail to be the new node
else: # Oherwise...
# Set the prev property on the head of the list to be the new node
self.head.prev = newNode
# Set the next property on the new node to be the head property
newNode.next = self.head
# Update the head to be the new node
self.head = newNode
self.length = self.length + 1 # Increment the length
return self

def pop_left(self):
# If length is 0, return undefined
if self.length == 0:
return "Undefined"
else:
# Store the current head property in a variable (we'll call it old head)
old_head = self.head
# If the length is one
if self.length == 1:
# Set the head to be null
self.head == None
# set the tail to be null
self.tail == None
# Update the head to be the next of the old head
self.head = old_head.next
# Set the head's prev property to null
self.head.prev = None
# Set the old head's next to null
old_head.next = None
# Decrement the length
self.length = self.length - 1
# Return old head
return old_head

def cust_get(self, item_location):

if item_location < 0 or item_location >= self.length:
return None

if item_location <= (self.length // 2):
print("Traversing from start")
count = 0
current = self.head
while count != item_location:
current = current.next
count = count + 1
return current

elif item_location >= (self.length // 2):
print("Traversing backwards from end")
count = self.length -1
current = self.tail
while count != item_location:
current = current.prev
count = count - 1
return current

def cust_set(self, item_location, new_value):
found_node = self.cust_get(item_location)

if found_node != None:
found_node.value = new_value
return True
return False

def cust_insert(self, item_location, new_value):
if item_location < 0 or item_location > self.length:
return None
elif item_location == 0:
return self.add_left(new_value)
elif item_location == self.length:
self.add_right(new_value)
self.length += 1
# print(self.length)
return self
new_node = Node(new_value)
before_node = self.cust_get(item_location-1)
after_node = before_node.next
before_node.next = new_node
new_node.prev = before_node
new_node.next = after_node
after_node.prev = new_node
self.length = self.length + 1
return True

def cust_remove(self, item_location):
if item_location < 0: # or item_location > self.length:
return None
elif item_location == 0:
return self.pop_left()
elif item_location == (self.length-1):
return self.pop_right()
removed_node = self.cust_get(item_location)
removed_node.prev.next = removed_node.next
removed_node.next.prev = removed_node.prev
removed_node.next = None
removed_node.prev = None
self.length = self.length - 1
return removed_node

def __str__(self):
if self.length == 0:
return "Empty DLL for intialization"

current = self.head
elements = []
while current:
elements += [str(current.value)]
current = current.next

return "Doubly Linked List: [" + " <-> ".join(elements) + "]"

# Instantiation and testing

DLL_obj = DoublyLinkedList()
print(DLL_obj)
DLL_obj.add_right(7)
DLL_obj.add_right(12)
DLL_obj.add_right(22)
print(DLL_obj)
DLL_obj.cust_insert(0,999)
print(DLL_obj)
DLL_obj.cust_insert(4,90099)
print(DLL_obj)
DLL_obj.cust_insert(2,"'Custom insert test'")
print(DLL_obj)
# DLL_obj.cust_remove(2)
print(DLL_obj.cust_remove(2))

print(DLL_obj)
``````

Here are two other (failed) attempts I made at writing the `shift_linked_list()` function:

``````def shift_linked_list(DLL_obj,k):
if k > 0:
for iteration in range(0,k):
DLL_obj.cust_insert(0, DLL_obj.pop_right())
DLL_obj.cust_remove(len(DLL_obj)-1)
return DLL_obj

shift_linked_list(DLL_obj,2)

print(DLL_obj)
``````

And:

``````def shift_linked_list(DLL_obj,k):
if k > 0:
for iteration in range(0,k):
DLL_obj.add_left(DLL_obj[-1])
DLL_obj.pop_right(DLL_obj[0])
return DLL_obj
``````

You don’t have an absolute position, but you have a Node instance, so you already have prev and next pointers.
To remove the element you can simply update the left and right nodes, plus self.length and (if needed) self.head and/or self.tail
If you absolutely need an absolute position you can traverse the list from start until you find the node

Hi,

you can try something like this:

``````class CircularLinkedList:

def __init__(self):

self.head = None
self.nodes = None
self.node_objects = []

def traverse(self, starting_point = None):

if starting_point is None:

starting_point = self.head

node = starting_point

while node is not None and (node.next != starting_point):

yield node
node = node.next

yield node

def print_list(self, starting_point = None):

self.nodes = []

for node in self.traverse(starting_point):
# nodes.append(str(node))       # Shows node object
self.nodes.append(node.data)    # Append node data
self.node_objects.append(node)  # Append node object

print(" -> ".join(self.nodes))

# Reassigns the head node depending on the value of `k'
def shift_nodes(self, k_pos):

if abs(k_pos) < len(self.node_objects):
self.head = self.node_objects[k_pos]
else:
print("'k' value entered exceeds nodes in linked list!")

class Node:

def __init__(self, data):

self.data = data
self.next = None
self.previous = None

circular_llist = CircularLinkedList()

# Create node objects
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")
g = Node("g")
h = Node("h")

# Set pointer to next node in sequence
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
f.next = g
g.next = h
h.next = a

# Define the head node for the linked list
circular_llist.head = a

# Print initial state of list
circular_llist.print_list()

def shift_linked_list(l_list, k):
l_list.shift_nodes(k)

shift_linked_list(circular_llist, -5)

# Print post shifted list
circular_llist.print_list()

``````

I borrowed the base code from a website of which I forgot to copy ( as soon as I find it I will copy the link). All I did was add an extra method (`shift_nodes`) and two attributes to the `CircularLinkedList` class, and added the function by which to pass the two required parameters: the linked list and the `k` argument.

Here is the tutorial where I found the base code:

I will not delve much into the theory as the tutorial explains it pretty well.

By the way, it is technically incorrect to call it a `Singly Linked List` as that would imply a one way pointer for every node. The correct terminology would be `Circular Linked List` as per the figure below since the tail node points to the first node:

Thank you both for your replies.

This is a good observation. In keeping with the DRY principal, in my latest attempts (two of them below), I reworked my function by embedding it into my original Doubly Linked List class so it it inherits all the properties including `self.left` / `self.right` / `Node`

In my latest two attempts, I didn’t see the requirement of updating `self.length` because in the context of the coding challenge, I am merely moving a list item from the right end to the left end. This means that the length should always remain the same since I am not remove or adding, just repositioning.

Having said all of that, here is my best attempt:

``````    def shift_linked_list(self, variance):
if variance > 0:
for iteration in range(0,variance):
self.head = self.tail
# self.length = self.length + 1
return self
elif variance < 0:
for iteration in range(0,variance):
self.tail = self.head
# self.length = self.length - 1
return self
elif variance == 0:
pass
``````

To test, I build the DLL, print the the DLL, cast the method, and print the new DLL. This gives me a before and after snapshot:

``````DLL_obj = DoublyLinkedList()
DLL_obj.add_right(7)
DLL_obj.add_right(12)
DLL_obj.add_right(22)
DLL_obj.cust_insert(0,999)
DLL_obj.cust_insert(4,90099)
DLL_obj.cust_insert(2,"'Custom insert test'")
print(DLL_obj)

DLL_obj.shift_linked_list(5)
print(DLL_obj)
``````

Here is my expected output:

``````python script11.py
Traversing from start
Doubly Linked List: [999 <-> 7 <-> 'Custom insert test' <-> 12 <-> 22 <-> 90099]
Doubly Linked List: [22 <-> 90099 <-> 999 <-> 7 <-> 'Custom insert test' <-> 12 ]
``````

Here is my actual output in my shell:

``````python script11.py
Traversing from start
Doubly Linked List: [999 <-> 7 <-> 'Custom insert test' <-> 12 <-> 22 <-> 90099]
Doubly Linked List: [90099]
``````

Take notice that in my expected output the two end values are added to the front but in the actual output it is returning just the single node from the end. I clearly still have issues and I believe the self.length value isn’t it.

Here is a rewrite of the method as my next attempt:

``````    def shift_linked_list(self, variance):

if variance > 0:
for iteration in range(0,variance):
# Store the current tail in a variable to add later
temp = self.tail
# Reassign prev as new tail
self.tail = self.tail.prev
# Set the new tail's next to null
self.tail.next = None
# self.length = self.length - 1
self.head = temp
return self

elif variance < 0:
for iteration in range(0,variance):
self.tail = self.head
# self.length = self.length + 1
return self

elif variance == 0:
pass
``````

As you can see, this time I am reassigning `prev` and `next` values to the end.

Here is my output now:

``````python script12.py
Traversing from start
Doubly Linked List: [999 <-> 7 <-> 'Custom insert test' <-> 12 <-> 22 <-> 90099]
Doubly Linked List: [22]
``````

That is progress because now the variance value is being processed properly. I am getting the second last list item rather than the first. If I change the variance to `3` it returns `12`. While this may be a slight improvement, what I really need is my method to return the full list rather than just the one node. What might you people suggest I try to next to achieve that? How close am I to the desired outcome?

Based on the description of the challenge I outlined initially and based on the article you shared, I can see why a “Circular Linked List” kind of makes sense, but the actual original challenge in context I encountered on AlgoExpert as a fair-use “freebie”. This means that Singly Linked List is the right terminology. As I explained originally as well, I in my case I am attempting to write this method on a Doubly Linked List and then afterwards will reimplement as Singly.

Although while I appreciate @onePythonUser sharing their advice and the article, please be advised that I am trying to learn how to write algorithms in Python and by providing all the code kind of ruins the educational experience for me. For anyone reading this, I am asking for your advice, recommendations, feedback, and hints without other forum members providing the entire solution for me. The response that @rgh is perfect because I welcome pseudo code. Further insight along those lines is what I am looking forward to.

Well, you’re trying to make your job easier by using a doubly linked list.
This is a good idea, but for it to work properly the last and first nodes should be connected as well (i.e. head.prev = tail, tail.next=head), making it a circular linked list.
The second attempt doesn’t work because tail.next and head.prev are both None.
The loop updates the head, tail and new tail.next pointers, but it should also update temp.next and head.prev.

Thank you for your reply.

For the second attempt, you’re right when you observe that I was pointing to `None`. That’s not where I want to be. You suggested that I should be updating `temp.next` and `head.prev`. I experimented with that and encountered a perpetual loop. I tried a few different variations. No dice.

Here was on such next attempt:

``````    def shift_linked_list(self, variance):

if variance > 0:
for iteration in range(0,variance):
# Store the current tail in a variable to add later
temp = self.tail
# Reassign prev as new tail
self.tail = self.tail.prev
# Set the new tail's next to head
temp.next = self.head
# self.head.prev = self.tail
self.tail.next = self.head
return

elif variance < 0:
for iteration in range(0,variance):
self.tail = self.head
# self.length = self.length + 1
return self

elif variance == 0:
pass
``````

I realize that is all wrong because I played around using my debugger as I watched the interpreter build a list with the same variable, over and over. I have a lot of work cut out for me as I continue to use my debugger and rubber ducky my way through the next iteration of my algorithm.

The material from the platform gives this hint:

HINT: There are four nodes that really matter in this entire process: the original tail of the linked list, which will point to the original head of the linked list, the original head of the linked list, which will be pointed to by the original tail of the linked list, the new tail of the linked list, and the new head of the linked list. Note that the new head is the node that the new tail points to in the original, unshifted linked list.

This provides a lot of additional clarity and gives me some more leads to work with. I don’t have enough time today but I will return with more experimentation when I can.

Thank you @rgh for your suggestions so far.

In the posted attempt you set both `temp.next` and `tail.next` to the same element.
Obviously it cannot work, because temp is the previous tail and tail is now the new element. temp.next should point to the new tail.
But I’m not sure what is your current list implementation. If you are using a circular list (as `tail.next = self.head` suggests) shifting can be implemented by just updating the head/tail pointers. Shifting doesn’t really move the elements, it’s just changing the head (and consequently, tail) position.
If you are still using the previous implementation, were tail.next was None, then shifting means changing the elements, as you are trying to do in your example.
At this time, however, I suggest you first draw the list on a piece of paper before and after a single shift. It will be much easier to understand how to implement the changes.

While I didn’t draw a diagram on paper, earlier I shared my expected (desired) output and broken actual output. That was a few posts ago and this thread is rather verbose, so I can’t blame you for missing it, @rgh . Here it is again with some slight reformatting.

Original DLL output:

`````` [999 <-> 7 <-> 'Custom insert test' <-> 12 <-> 22 <-> 90099]
``````

Desired DLL after one shift of last element to front of DLL:

``````[ 90099 <-> 999 <-> 7 <-> 'Custom insert test' <-> 12 <--> 22 ]
``````

That is what I am trying to accomplish. I understand the objective clearly.

Back to basics, I tried moving the `self.head` and `self.tail` pointers as you’ve suggested in this way:

``````    def shift_linked_list(self, variance):

if variance > 0:
for iteration in range(0,variance):
temp_end = self.tail
temp_front = self.head
self.head = temp_end
self.tail = temp_front
return
``````

When I cast `DLL_obj.shift_linked_list(1)`, the output shows: `90999`.

Here is another stab in the dark:

``````    def shift_linked_list(self, variance):

if variance > 0:
for iteration in range(0,variance):
# temp_end = self.tail
# temp_front = self.head
self.head = self.tail
self.tail = self.head
return
``````

Same output as the last one, just a single element is returned: `090999`.

Based on the “HINT” I quoted above, I feel like I am doing as it suggests as well as what @rgh is suggesting exactly:

I’ve checked all of those boxes in my code as far as I can tell.

Here is what remains outstanding for me to complete which I am at a loss for:

Here is another try:

``````    def shift_linked_list(self, variance):

if variance > 0:
for iteration in range(0,variance):
self.tail.next = self.head
self.head.prev = self.tail
return
``````

That one loops infinitely and returns nothing.

Hi, I was suggesting to draw the linked list on paper to help you visualize how the pointers need to be updated to achieve your objective.
You called one of the attempts “another stab on the dark”. Drawing the changes on paper should help you identify exactly what steps are needed, instead of blindly trying code changes.
For example, the last try simply repeats `tail.next = head and head.prev = tail` variance times.
But in a circular doubly linked list tail.next is already equal to the head element. Ditto for head.prev and tail.
If you like a nice discussion of linked lists, perhaps this article could be useful https://www.geeksforgeeks.org/introduction-to-circular-doubly-linked-list/