CODEWITHSUNDEEP
pythonalgorithmlinked-list
123
123

Reputation: 8951

Reverse link direction of singly linked list

I have a linked list that is reverse linked, is there a way I can change the direction of the links in this program? I've tried using self.head.set_next starting at the first element, but type None doesn't have a method set_next, so I'm not sure how I would proceed.

class Node2(object):
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

    def set_next(self, new_next):
        self.next_node = new_next

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next_node

class LinkedList2(object):
    def __init__(self, head=None):
        self.head = head

    def insert(self, data):
        new_node = Node(data)
        new_node.set_next(self.head)
        self.head = new_node

Upvotes: 1

Views: 254

Answers (2)

Salomé
Salomé

Reputation: 1978

Something like that would do the trick

# linked_list is the list you want to reverse
previous_node = None
current_node = linked_list.head

while current_node is not None:
    next_node = current_node.get_next()
    current_node.set_next(previous_node)
    previous_node, current_node = current_node, next_node

linked_list.head = previous_node

This will execute in linear time.

However, if you find you need to frequently reverse linked list, you may find doubly linked lists to be more adapted to your needs

Upvotes: 3

Garrett R
Garrett R

Reputation: 2662

You can do it recursively as well:

prev_node = 
cur_node = linked_list.head

def reverse_ll(prev, cur):
    if not cur: return prev
    next_node = cur.get_next()
    cur.set_next(prev)
    return reverse_ll(cur, next_node)

reversed_head = reverse_ll(None, cur_node)

Upvotes: 0

Related Questions