用Java实现单链表的基本操作

笔试题中经常遇到单链表的考题，下面用java总结一下单链表的基本操作，包括添加删除节点，以及链表转置。

package mars;

//单链表添加，删除节点

public class ListNode {

    private Node head;

    public ListNode(){

        head=null;

    }

    //在链表前添加节点

    public void addpre(int dvalue){

        Node n=new Node(dvalue);

        if(head==null){

            head=n;

        }else{

            n.next=head;

            head=n;

        }

    }

    //在链表后添加节点

    public void add(int dvalue){

        Node n=new Node(dvalue);

        Node current = head;

        while(current!=null){

            if(current.next==null){

                current.next=n;

                return;

            }

            current=current.next;

        }

    }

    //删除值为dvalue的节点

    public Node delete(int dvalue){

        Node current=head;

        if(head.value==dvalue){

            head=head.next;

            return current;

        }

        while(current.next!=null){

            if(current.next.value==dvalue){

                Node temp=current.next;

                current.next=temp.next;

                return temp;

            }

            current=current.next;

        }

        return null;

    }

    //删除特定位置的节点

    public Node deletepos(int pos){

        Node current=head;

        int counter=0;

        if(pos==0){

            head=head.next;

            return current;

        }

        while(current!=null){

            if((counter==(pos-1))&&(current.next!=null)){

                Node temp=current.next;

                current.next=temp.next;

                return temp;

            }

            current=current.next;

            counter++;

        }

        return null;

    }

    //单链表转置

    public void reverse(){

        Node a=head;

        if(a==null){

            return ;

        }

        Node b=head.next;

        if(b==null){

            return ;

        }

        Node c=head.next.next;

        a.next=null;

        while(c!=null){

            b.next=a;

            a=b;

            b=c;

            c=c.next;

        }

        b.next=a;

        head=b;

    }

    //输出链表信息

    public void print(){

        Node current = head;

        while(current!=null){

            System.out.println(current.value);

            current=current.next;

        }

    }

    public static void main(String[] args){

        ListNode l=new ListNode();

        l.addpre(3);

        l.addpre(2);

        l.addpre(1);

        l.add(7);

        l.add(8);

        l.add(9);

        l.delete(1);

        l.deletepos(4);

        l.reverse();

        l.print();

    }

}

class Node{

    public Node next;

    public int value;

    public Node(){

        next=null;

    }

    public Node(int v){

        value=v;

    }

}

PS：Java的引用类似于C的指针，例如 :

Node n1=new Node(1); Node n2=n1; Node n3=new Node(3); n2=n3;

执行n2=n1后，n1和n2都是对同一块内存区域（区域1）的引用，通过n1和n2都可以达到修改内存区域1的目的，例如执行n1.value=10后，输出n2.value的值也为10。但是执行n2=n3后，n2则变为了对另一块内存区域（区域3）的应用。

巴特西

用Java实现单链表的基本操作

最新文章

热门文章