筆試題中經常遇到單鏈表的考題,下面用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)的應用。