algorithm - 按引用或按值链接列表？

Question

问题来了。假设链表实现如下(Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

考虑链表:

1 -> 2 -> 3 -> 4

我做了类似的事情:

ListNode newHead = head;
newHead = head.next.next; 
//Now newHead is pointing to (3) in the linked list.

现在我施展魔法:

newHead.val = 87

链表变为:

1 -> 2 -> 87 -> 4

如果我打印了 head 和 NOT newHead。

这是为什么？我没有用 head 修改任何东西，它仍然改变了？

Answer 1

所以你可以使用这个:

节点类:

public class IntNode {

    int value;
    IntNode next;

    public IntNode(int value) {
        this.value = value;
    }
}

单链表类:

/**
 * A singly-linked list of integer values with fast addFirst and addLast methods
 */
public class LinkedIntList {

    IntNode first;
    IntNode last;
    int size;

    /**
     * Return the integer value at position 'index'
     */
    int get(int index) {
        return getNode(index).value;
    }

    /**
     * Set the integer value at position 'index' to 'value'
     */
    void set(int index, int value) {
        getNode(index).value = value;
    }

    /**
     * Returns whether the list is empty (has no values)
     */
    boolean isEmpty() {
        return size == 0;
    }

    /**
     * Inserts 'value' at position 0 in the list.
     */
    void addFirst(int value) {
        IntNode newNode = new IntNode(value);
        newNode.next = first;
        first = newNode;
        if(last == null)
            last = newNode;
        size++;
    }

    /**
     * Appends 'value' at the end of the list.
     */
    void addLast(int value) {
        IntNode newNode = new IntNode(value);
        if(isEmpty())
            first = newNode;
        else
            last.next = newNode;

        last = newNode;
        size++;
    }

    /**
     * Removes and returns the first value of the list.
     */
    int removeFirst() {
        if(isEmpty()) {
            System.out.println("RemoveFirst() on empty list!");
            System.exit(-1);
        }

        int value = first.value;
        if(first == last) {
            // List has only one element, so just clear it
            clear();
        }
        else {
            first = first.next;
            size--;
        }

        return value;
    }

    /**
     * Removes and returns the last value of the list.
     */
    int removeLast() {
        if(isEmpty()) {
            System.out.println("RemoveLast() on empty list!");
            System.exit(-1);
        }

        int value = last.value;
        if(first == last) {
            // List has only one element, so just clear it
            clear();
        }
        else {
            // List has more than one element
            IntNode currentNode = first;
            while(currentNode.next != last)
                currentNode = currentNode.next;

            currentNode.next = null;
            last = currentNode;
            size--;
        }
        return value;
    }

    /**
     * Removes all values from the list, making the list empty.
     */
    void clear() {
        first = last = null;
        size = 0;
    }

    /**
     * Returns a new int-array with the same contents as the list.
     */
    int[] toArray() {
        int[] array = new int[size];
        int i = 0;
        for(IntNode n = first; n != null; n = n.next, i++)
            array[i] = n.value;
        return array;
    }

    /**
     * For internal use only.
     */
    IntNode getNode(int index) {
        if(index < 0 || index >= size) {
            System.out.println("GetNode() with invalid index: " + index);
            System.exit(-1);
        }

        IntNode current = first;
        for(int i = 0; i < index; i++)
            current = current.next;
        return current;
    }
}

说明见代码注释