Reverse Linked List (reference to next node)

Question

I'm working on a question which is asking to reverse a linked list:

Example:

For linked list 1->2->3, the reversed linked list is 3->2->1

Here is my code:

"""
Definition of ListNode

class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of the linked list.
    @return: You should return the head of the reversed linked list. 
                  Reverse it in-place.
    """
    def reverse(self, head):
        # write your code here
        prev = None
        current = head
        next = current.next
        while(current is not None):
            current.next = prev
            prev = current
            current = next
            next = next.next
        head = prev
        return prev

After submit I got error. Could anyone help me to point out why it is wrong? The error message is saying that "next = current.next AttributeError: 'NoneType' object has no attribute 'next'". I tried to use next refer to the node next to the current node.

Thanks!

Duplicate of - https://stackoverflow.com/questions/21529359/reversing-a-linked-list-in-python?rq=1 — Dror Av., Aug 11 '17 at 08:12
I think you need to check if head is None before doing your logic. In case of head is None you just need to return it. — Vitalie Maldur, Aug 11 '17 at 08:13
Always consider all kinds of testcases. For example, empty list, list with one,two...items, etc. — lincr, Aug 11 '17 at 08:16
@droravr it is not a duplicate of that question. Both questions deal with reversing linked lists, but the specific issues are different. — Miriam Farber, Aug 11 '17 at 08:20
@VitalieMaldur : Nope - see answer by Miriam Farber which avoids any special cases. (First rule of linked list code: "No special cases" - you will miss one.) — Martin Bonner supports Monica, Aug 11 '17 at 08:28
@MiriamFarber, A linked list is a linked list. Thats why in the end the answer on this post is exactly the same as to the one in the link. — Dror Av., Aug 11 '17 at 08:35
@droravr the idea is not only to show how to reverse a linked list (there are many online solutions for that). The idea is also to point out the specific problem with the OP's code. — Miriam Farber, Aug 11 '17 at 08:38

Miriam Farber · Accepted Answer · 2017-08-11T08:34:30.697

5

You are trying to access next.next, but next may be None (you checked if current is None, but you didn't check if next is None. next will indeed be None in the last iteration of the loop). Thus, you need to move next=current.next inside the loop, and remove the last row in the loop, as follows:

def reverse(self, head):
        # write your code here
        prev = None
        current = head
        while(current is not None):
            next = current.next
            current.next = prev
            prev = current
            current = next
        return prev

edited Aug 11 '17 at 08:34

answered Aug 11 '17 at 08:16

Miriam Farber

18,986
14
61
76

Got it now. THANKS Miriam!! – Xiang Li Aug 11 '17 at 08:26
1

**This** is the right answer - note that there are no special cases. One quibble, there is no point in assigning to `head` before you return - it is a local variable. – Martin Bonner supports Monica Aug 11 '17 at 08:26

score 0 · Answer 2 · answered Aug 11 '17 at 08:16

The issue occurs at the very last case. When current equals the last node in the list, you go to assign next to equal next.next. The problem is that next at this point is equal to null, so your saying null is equal to null.null which is causing your error. Vou should probably change your while loop condition to

while(next is not None):

and change add in a section after to update the final node in the list to point to the previous one

current.next = prev
head = prev
return prev

Reverse Linked List (reference to next node)

2 Answers2