笔试题中经常遇到单链表的考题,下面用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();
}
}