Reverse the nodes in linked list with stack .why the new linked list become so large?

Question

I want to reverse nodes in a linked list with stack.so I first create a linked list:

head = ListNode(0)
temp = head
temp.next = ListNode(1)
temp = temp.next
temp.next = ListNode(2)

then I use stack to store the list nodes, then pop them to a new linked list new_tail to reverse the given linked list.

dummy_node = ListNode(0)
cur = head
new_tail = dummy_node
while cur:
    i = 0
    tmp_sk = [] # use the stack to store the elements of linked list
    tmp_tail = cur 
    while i < 3:        
        if cur:
            tmp_sk.append(cur)
            cur = cur.next
            i +=1
        else:
            new_tail.next = tmp_tail
            break
    while tmp_sk:
        new_tail.next = tmp_sk.pop()
        new_tail = new_tail.next

but something strange happened. when I try to print the new linked list, the list is very large.

count = 0
new = dummy_node
while new:
    count+=1
    print(new.val)
    new = new.next

the count can be a large number and the print can't stop util I intervene. I couldn't find where the problem.

Answer 1

Several issues:

• The main issue is that the last node that is appended in the while tmp_sk loop, will still have a next reference that is not reset. So when the while tmp_sk has finished, you have a linked list whose last node is new_tail, but that node is not really a tail: it has a next reference that never got updated, and refers to the node that was originally the second node, and is now the one-but-last node. And so there is a cycle now. The solution is to perform new_tail.next = None right after that loop.

• The inner loop should not have i < 3 as condition. This will only work when your list has three nodes. You should make this generic, and test for cur instead. This also means that the else block in that loop will never be executed. It should just be omitted.

• The outer loop while cur: serves no purpose. Once that loop has made one iteration, it will always exit. It wouldn't make sense if it would make a second iteration and restart with a new stack, etc. So remove that loop and just keep its body.

• The part where you print the list, also prints the value of the dummy node. I don't suppose that is the purpose; so skip that first node.

• Not a problem, but you should divide your code into functions, where each function is responsible for one task: create the list, reverse the list, print the list.

Here is the correction and clean up of your code:

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

def createList(values):
    # initialise list (generic - from a list of values)
    node = dummy = ListNode(None)
    for val in values:
        node.next = ListNode(val)
        node = node.next
    return dummy.next

def reverseList(head):
    cur = head
    tmp_sk = [] # use the stack to store the elements of linked list
    while cur:
        tmp_sk.append(cur)
        cur = cur.next

    dummy_node = ListNode(None)
    new_tail = dummy_node
    while tmp_sk:
        new_tail.next = tmp_sk.pop()
        new_tail = new_tail.next
    new_tail.next = None # this was missing!
    return dummy_node.next  # return the new head

def printList(head):
    cur = head
    while cur:
        print(cur.val)
        cur = cur.next

# main program
head = createList([0, 1, 2])
head = reverseList(head)
printList(head)