JAVA链表基本操作

和C版对应

/*链表常用操作*/
class LinkNode
{
    /*
     * 链表常用操作类
     * 无头结点链表
     */

    //结点定义
    static class Node
    {
        Node(int data)
        {
            this.data = data;
        }
        int data;
        Node next = null;
    }

    //从输入流建链表
    static Node createLinkList()
    {
        Scanner scanner = new Scanner(System.in);
        int data = scanner.nextInt();
        Node head = new Node(data);
        Node p = head;
        //直到输入的值不为整数则结束读入
        while (scanner.hasNextInt())
        {
            data = scanner.nextInt();
            Node node = new Node(data);
            p.next = node;
            p = node;
        }
        scanner.close();
        return head;
    }

    //快速新建下一个头结点
    static void fastCreateNode(Node head,int data)
    {
        Node p = new Node(data);
        head.next = p;
    }

    //建立默认链表：5 2 1 3 4
    static Node fastCreateDefaultList()
    {
        Node linkList = new Node(5);
        LinkNode.fastCreateNode(linkList,2);
        LinkNode.fastCreateNode(linkList.next,1);
        LinkNode.fastCreateNode(linkList.next.next,3);
        LinkNode.fastCreateNode(linkList.next.next.next,4);
        return linkList;
    }

    //打印链表
    static void printLinkList(Node head)
    {
        Node p = head;
        while(p.next!=null)
        {
            System.out.print(p.data+" ");
            p = p.next;
        }
        System.out.println(p.data);
    }

    //反转打印链表
    static void reversePrintLinkList(Node head)
    {
        if (head.next!=null)
            reversePrintLinkList(head.next);
        System.out.print(head.data+" ");
    }

    //在指定位置添加结点
    static void addNode(Node head,int position,int data)
    {
        Node p = head;
        //特殊情况，添加结点为首节点，position=0
        if (position==0)
        {
            Node headexgNode = new Node(head.data);
            headexgNode.next = head.next;
            head.next = headexgNode;
            head.data = data;
            return;
        }
        for(int i=0; i<position-1; i++)
            p = p.next;
        //p和p.next中间插一个新结点
        Node newNode = new Node(data);
        newNode.next = p.next;
        p.next = newNode;
    }

    //删除结点
    static void deleteNode(Node head,int position)
    {
        Node p = head;
        //特殊情况，删除头结点
        if (position==0)
        {
            head.data = head.next.data;
            head.next= head.next.next;
            return;
        }
        for (int i=0; i<position-1; i++)
            p = p.next;
        //删除p.next结点
        p.next = p.next.next;
    }

    //反转链表
    static Node reverseLinkList(Node head)
    {
        Node p=head,q=head.next;
        while(q.next!=null)
        {
            Node temp = q.next;
            q.next = p;
            p = q;
            q = temp;
        }
        //处理头结点head
        head.next = null;
        //注意这里,这句容易漏，漏了的话最后的头结点就是个单节点了
        q.next = p;
        return q;
    }
}