头插法代码示例

public class LinkDemo {
    public static void main(String[] args) {
        //将这个数组按头插的方式插入列表
        int[] arr={1,2,3,4,5,6,7,8,9};
        headIndert(arr);
    }

    public static void headIndert(int[] arr){
        Node link=null;
        for (int i = 0; i < arr.length; i++) {
            Node x=new Node();
            x.value=arr[i];
            x.next=link;
            link=x;
        }
        System.out.println(link);
    }
}

public class Node {
    public int value;
    public Node next;

    public String toString(){
        return "值是："+value+"，下一个节点是："+next;
    }
}

对应内存图

• 当i=0,第一次循环

• 第一次循环结束，回收循环体内的变量x

• i=1，第二次循环

• 第二次循环结束，回收循环体内变量x

循环两次后当前链表为：

• 接着进行循环，直至到达循环停止条件
• .........
• 这个循环在外的变量也相当于头指针，指向链表的第一个节点

尾插法代码示例

public static void fun(int[] arr){
    Node link=null;
    for (int i = arr.length-1; i >=0 ; i--) {
        Node x=new Node();
        x.value=arr[i];
        x.next=link;
        link=x;
    }
    System.out.println("尾插");
    System.out.println(link);
}

//尾插法
public static void addLast(int[] arr){
    ListNode head=null;
    for (int i = 0; i < arr.length; i++) {
        ListNode newnode = new ListNode(arr[i]);
        if (head == null) {
            head = newnode;
        } else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newnode;
        }
    }
    System.out.println(head);
}

• 注意遍历单链表的时候，循环条件英高是cur.next != null，而不是cur != null，前者指节点的next域为空，后者指整个节点为空。