package com.company;

import java.util.ArrayList;
class Node{
    public Node(int val, Node next){
        this.val = val;
        this.next = next;
    }
    public Node(int val){
        this(val, null);
    }
    int val;
    Node next;

    private void setVal(int newVal){
        this.val = newVal;
    }

    private void setNext(Node newNextNode){
        this.next = newNextNode;
    }
}

public class MyCodeLink {
    private Node head;
    private int size;
    public MyCodeLink(int val){
        this.head = new Node(val, null);
        this.size = 1;
    }

    public void insert(int index, int val){
        if (index < 0 || index > this.getSize()){
            throw new IndexOutOfBoundsException("index must >= 0 and <= size");
        }
        if (index == 0){
            this.head = new Node(val, head);
            this.size  ;

            return;
        }


        Node cur = head;
        for (int i = 0; i < index - 1; i  ){
            cur = cur.next;
        }

        Node node = new Node(val, cur.next);
        cur.next = node;
        this.size  ;
    }

    public void insertToHead(int val){
        insert(0, val);
    }
    public void insertToLast(int val){
        insert(this.getSize(), val);
    }

    public int getSize(){
        return this.size;
    }

    public Node getHead(){
        return head;
    }

    @Override
    public String toString(){
        StringBuilder s = new StringBuilder();
        Node cur = head;
        while (cur != null){
            s.append(cur.val).append("\t");
            cur = cur.next;
        }

        return s.toString();
    }

    public void reversal(){
//        they will throw `java.lang.OutOfMemoryError: Java heap space` too!
//        Node cur = this.head;
//        ArrayList<Node> stack = new ArrayList<Node>();
//
//        while (cur.next != null){
//            stack.add(cur);
//            cur = cur.next;
//        }
//
//        this.head = cur;
//
//        while (!stack.isEmpty()){
//            cur.setNext(stack.remove(stack.size() - 1));
//            cur = cur.next;
//        }
        Node p1 = this.head;
        Node p2 = p1.next;

        while (p2 != null){
            Node temp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = temp;
        }

        this.head = p1;

    }

    public static void main(String[] args){
        MyCodeLink myCodeLink = new MyCodeLink(8);

        System.out.println("size: "   myCodeLink.getSize());
        System.out.println(myCodeLink);

        myCodeLink.insertToHead(6);
        System.out.println("size: "   myCodeLink.getSize());
        System.out.println(myCodeLink);

        myCodeLink.insert(1, 7);
        System.out.println("size: "   myCodeLink.getSize());
        System.out.println(myCodeLink);

        myCodeLink.insertToLast(9);
        System.out.println("size: "   myCodeLink.getSize());
        System.out.println(myCodeLink);

        myCodeLink.reversal();
        System.out.println("size: "   myCodeLink.getSize());
        System.out.println(myCodeLink);
    }

}

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.base/java.util.Arrays.copyOf(Arrays.java:3537)
    at java.base/java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:228)
    at java.base/java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:829)
    at java.base/java.lang.StringBuilder.append(StringBuilder.java:253)
    at com.company.MyCodeLink.toString(MyCodeLink.java:74)
    at java.base/java.lang.String.valueOf(String.java:4218)
    at java.base/java.io.PrintStream.println(PrintStream.java:1047)
    at com.company.MyCodeLink.main(MyCodeLink.java:132)

I'm learning about linked list and this problem arose when I implemented reverse linked list

I tried to implement the reversal method in other ways, they have been commented.

what happen with this code?

I also tried compiling this code with other versions of Java, the result is the same

This should be my problem, but I really can't figure out why

CodePudding user response：

I outlined the problem in the comments already: your reversal implementation is wrong, you end up with the originally first and second element pointing to each other.

I would recommend to choose better elements than p1 and p2 to make it clear what element you are currently working on. The following might make it more clear

Node current = this.head; // we start at the head
Node previous = null; // and the previous of head should be null after the reversal

while (current != null){
    Node temp = current.next; // save the next node
    current.next = previous; // point the current node back instead of forward
    previous = current; // set the new previous node
    current = temp; // move one forward
}

this.head = previous; // current is null by now