Question about Reverse Linked List (leetcode 206)

user_13004319 0
Viewed 97

I know my code is completely wrong, but I do not know where I did wrong,

can anyone point out and explain what I did wrong?

public ListNode reverseList(ListNode head) {
    if (head == null) {
        return head;
    }
    
    ListNode prev = null;
    ListNode current = head;
    ListNode nextNode = head.next;
    
    while (nextNode != null) {
        prev = current;
        current = nextNode;
        current.next = prev;
        nextNode = nextNode.next;
        System.out.println(nextNode.val);
    }
    
    return current;
}
data-structures linked-list algorithm
2 Answers

Changes:

  1. head.next = null; // to make the end of the list as null

  2. current.next = prev; // current is the reference to the node so changes to it will change node with reference nextNode also

    public ListNode reverseList(ListNode head) {
     if (head == null) {
         return head;
     }

     ListNode prev = null;
     ListNode current = head;
     ListNode nextNode = head.next;
     head.next = null;   // to make the end of the list as null

     while (nextNode != null) {
         prev = current;
         current = nextNode;
         nextNode = nextNode.next;   // first get next node, before ...
         current.next = prev;        // ... overwriting it here
         // System.out.println(nextNode.val);
     }

     return current;
 }
user_136519780

Alternative Solution

We can just say while head != null and then reverse it using a prev Node, finally we would return the prev. It'd be easier:

public final class Solution {
    public static final ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode nextNode;

        while (head != null) {
            nextNode = head.next;
            head.next = prev;
            prev = head;
            head = nextNode;
        }

        return prev;
    }
}
user_65533280
Related