I'm working on the following problem Reverse Linked List from Leetcode:

Given the head of a singly linked list, reverse the list, and return the reversed list.

Class ListNode defined as follows:

 public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Here is the solution that I came up with.

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head != null) {
            ListNode pre = head;
            ListNode cur = head.next;
            ListNode temp;
            while (cur != null) {
                temp = cur.next;
                cur.next = pre; 
                pre = pre.next; //here should be pre = cur; but I don't get it.
                cur = temp;
            }
            head.next = null;
            return pre;
        } else {
            return null;
        }
    }
}

To make it working inside the while-loop, I need change

pre = pre.next;

with

pre = cur;

But I still don't fully understand it.

After temp = cur.next;, variable pre should still be pointing to cur, right?

So what's wrong here? Can someone explain it in detail?

CodePudding user response：

If you need to reverse singly linked list than I can give you a simpler solution

public class ListReverser {
    public static Node<Integer> reverse(Node head) {
        Node current = head;
        while(current.getNext() != null) {
            Node next =  current.getNext();
            current.setNext(next.getNext());
            next.setNext(head);
            head = next;
        }
        return head;
    }
}

I wrote a small post on my LinkedIn page with this solution. Feel free to visit: Popular Java interview task: Reverse singly (one-directional) linked list

CodePudding user response：

pre should still be pointing to cur, right? So what's wrong here?

pre = pre.next; // here should be pre = cur; but I don't get it.

When the while-loop terminates, cur points to null, so you need a reference to the previous node pre as a result.

Now let's take a closer look at the statement

pre = pre.next;

During the first step of iteration when pre points to head, this statement would be the same as pre = cur (effectively head.next). That fine.

But starting from the second iteration step, pre.next would point backwards, and that not what you need. You need to advance the reference pre to the tail (which would became a new head), not the opposite.

For that reason, you need pre = cur; instead.

You can get rid of the if-statement in your code and reimplement it like this:

public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

main()

public static void main(String[] args) {
    ListNode second = new ListNode(3);
    ListNode first = new ListNode(2, second);
    ListNode head = new ListNode(1, first);

    ListNode newHead = reverseList(head);
    while (newHead != null) {
        System.out.println(newHead.val);
        newHead = newHead.next;
    }
}

Output:

3
2
1

A link to Online Demo