The linked list does not loop repeatedly during the loop when using the following method

Question

I am trying to flip a linked list iteratively using a stack. I determined where the problem is, but for the life of me, I can’t understand why the code does not iterate correctly when I call the following ListNode method. I noted in the code below where the error occurs.

This is the result when I run the code:

Before: 1->2->3->4->null
After: 4->3->3->4->null

Here's what you should get:

Before: 1->2->3->4->null
After: 4->3->2->1->null

Can someone point me in the right direction regarding what is happening? Thank!

Here is the code:

public class Solution {
    public static void main(String[] args) {
        private static Solution soln = new Solution();
        ListNode head = makeLinkedList(4);

        System.out.print("Before: ");
        printLinkedList(head);
        System.out.println();

        soln.reverseList(head);

        System.out.print(" After: ");
        printLinkedList(head);

        System.exit(0);
    }

    public ListNode reverseList(ListNode head) {
        Stack<ListNode> listContents = new Stack<ListNode>();

        // iterate list and add to stack
        ListNode tmp = head;
        while (tmp != null) {
            listContents.push(tmp);
            tmp = tmp.next;
        }

        // iterate list again and replace each val with stack val
        tmp = head;
        while (tmp != null) {
            tmp.val = listContents.pop().val;
            // this is where the code seems to fail
            tmp = tmp.next; 
        }
        return head;
    }
}

How is a ListNode defined:

public class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int item) { 
        val = item; 
    }
}

This is how I create a linked list:

private static ListNode makeLinkedList(int numNodes) {
    ListNode head = null;
    ListNode tmp = null;
    for (int i = 1; i < numNodes + 1; i++) {
        if (tmp == null) {
            tmp = new ListNode(i);
            head = tmp;
        } else {
            tmp.next = new ListNode(i);
            tmp = tmp.next;
        }
    }
    return head;
}

Helper Method:

private static void printLinkedList(ListNode head) {
    ListNode tmp = head;
    while (tmp != null) {
        System.out.print(tmp.val + "->");
        tmp = tmp.next;
    }
    System.out.print("null");
}

Answer 1

Why is this not working?

, ListNode Stack . , , :

• ( ): 4 - 3 - 2 - 1
• , pop
  • : 4
  • : 3 - 2 - 4 ( )
• • : 4 - 3
  • : 3 - 4 ( node)
• • : 4 - 3 - 3
  • : 4
• • : 4 - 3 - 3 - 4

, ?

:

• .
• ListNode .
• , . , , Stack - . @xenteros.

Answer 2

, . :

public static ListNode reverseList(ListNode head) {
    // iterate list and add to stack
    ListNode current = head;
    ListNode previous = null;
    ListNode temp = null;
    while (current.next != null) {
        temp = previous;
        previous = current;
        current = current.next;
        previous.next = temp;
    }
    current.next = previous;
    return current;
}

. :

public static void main(String[] args) {

    ListNode head = makeLinkedList(4);

    System.out.print("Before: ");
    printLinkedList(head);
    System.out.println();

    head = reverseList(head);

    System.out.print(" After: ");
    printLinkedList(head);

    System.exit(0);
}

>>Before: 1->2->3->4->null
>>After: 4->3->2->1->null
>>Process finished with exit code 0

: node .

Answer 3

This is because you mutate your LinkedList without knowing it. In other words, when you rewrite the value more in your LinkedList, the nodes that you pushed on the stack earlier will also change. Therefore, one way to ensure that this does not happen is to create an instance and push a new node (copy) on the stack:

public ListNode reverseList(ListNode head) {
 Stack<ListNode> listContents = new Stack<ListNode>();

 // iterate list and add to stack
 ListNode tmp = head;

 while (tmp != null) {
     ListNode newNode = new ListNode(temp);
     listContents.push(newNode);
     tmp = tmp.next;
 }

 // iterate list again and replace each val with stack val
 tmp = head;
 while (tmp != null) {
     tmp.val = listContents.pop().val;
     tmp = tmp.next; 
 }
 return head;
}

A simple class modification ListNodeto add a copy constructor:

public class ListNode {
  int val;
  ListNode next = null;

  public ListNode (ListNode that){
     this.val = that.val;
      this.next = null;     //Could be that.next
   }

  public ListNode(int item) { 
      val = item; 
  }
}