Reverse linked list python

Question

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

class LinkedList:
    def __init__(self, input=None):
        self.first = None
        self.last = None
        self.index = None
        if input is not None:
            for p in input:
                new = Node(p)
                if self.first is None:
                    self.first = new
                else:
                    self.last.next = new
                self.last= new

This code makes a linked list from parameter.

t = LinkedList([1,2,[3,4],5])

will be stored as: 1-2-[3,4]-5 where - sign is data.next reference. I need reverse of this list, my idea was to swap elements [0]-[n],[1]-[n-1]..

def reverse(self):
    temp = self.first
    self.first = self.last
    self.last = temp
    temp = self.first.next

It swaps first and last element and makes temp as next node from start, but I don't know how to continue, how to make this code work ?

reverse is function of LinkedList, where self.first is declared in init function. — Jonatan
– Jonatan, Commented Mar 23, 2015 at 18:40
Tip: You can swap two variables x and y in Python without a temp variable using the statement x, y = y, x. — augurar
– augurar, Commented Mar 23, 2015 at 18:51

augurar · Accepted Answer · 2015-03-23 19:11:28Z

2

The general algorithm is as follows:

Maintain pointers to the start of two lists, an old list and a new list. Initially the old list contains all the nodes and the new list is empty.
Repeatedly remove the first node of the old list and add it to the front of the new list, until the old list is empty and the new list contains all nodes.

The resulting new list will be the reverse of the old list.

edited Mar 23, 2015 at 19:11

answered Mar 23, 2015 at 18:47

augurar

13.3k7 gold badges60 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

andrew · Accepted Answer · 2018-02-12 21:36:26Z

Here is an example of a working Node class and LinkedList class along with a reverse function that reverses the singly linked list in place. The idea is to change the memory references for each node.

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


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

    def reverse(self):
        current = self.head
        previous = None
        while current:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        self.head = previous

In one pass of the linked list, we swap the pointers of each node by keeping track of the current and previous nodes. This algorithm won't require a new linked list to be created to store the reversed list and will run in linear time. I hope this helps by giving an alternative linked list reverse implementation.

Ishaan · Accepted Answer · 2021-01-31 14:15:32Z

0

Modifying @andrew's solution by using recursion instead of iteration:

def reverse(self):
    def recursive(curr, prev):
        if not curr:  # curr is None
            return prev
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp

        return recursive(curr, prev)

    self.head = recursive(curr=self.head, prev=None)

answered Jan 31, 2021 at 14:15

Ishaan

11 bronze badge

Collectives™ on Stack Overflow

Reverse linked list python

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related