鏈表常見的操作：
1厚棵、插入節(jié)點(diǎn)（頭插、尾插）
2蔼紧、刪除節(jié)點(diǎn)
3窟感、獲取鏈表長(zhǎng)度
4、逆序打印
5歉井、反轉(zhuǎn)鏈表
6柿祈、判斷鏈表是否有環(huán)
7、判斷鏈表是否相交
8、如果相交躏嚎，返回第一個(gè)開始相交的節(jié)點(diǎn)
9蜜自、查找單鏈表中第K個(gè)節(jié)點(diǎn)
10、尋找單鏈表的中間結(jié)點(diǎn)
代碼外加注釋如下
class LinkList{
Node header;
static class Node{
int data;
Node next;
public Node(int data){
this.data = data;
}
}
/*
* 頭插法
* 被插入node的next指向header卢佣，則成為第一個(gè)
* 將header移動(dòng)到頭部
*/
public void addNodeHead(int data){
Node newNode = new Node(data);
if(header==null){
header = newNode;
}else{
newNode.next = header;
header = newNode;
}
}
/**
* 尾插法
*/
public void addNodeEnd(int data){
Node newNode = new Node(data);
if(header==null){
header = newNode;
}else{
Node temp = header;
while(temp.next!=null){
temp = temp.next;
}
temp.next = newNode;
}
}
/**
* 鏈表刪除結(jié)點(diǎn):
* 把要?jiǎng)h除結(jié)點(diǎn)的前結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的后結(jié)點(diǎn)重荠，即直接跳過待刪除結(jié)點(diǎn)
* @param index
* @return
*/
public boolean deleteNode(int index){
if(index<1 || index>getLength(header)){//待刪除結(jié)點(diǎn)不存在
return false;
}
if(index == 1){//刪除頭結(jié)點(diǎn)
header = header.next;
return true;
}
Node preNode = header;
Node curNode = preNode.next;
int i = 1;
while(curNode != null){
if(i==index){//尋找到待刪除結(jié)點(diǎn)
preNode.next = curNode.next;//待刪除結(jié)點(diǎn)的前結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的后結(jié)點(diǎn)
return true;
}
//當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
preNode = preNode.next;
curNode = curNode.next;
i++;
}
return true;
}
/**
* 長(zhǎng)度
* @param header
* @return
*/
public int getLength(Node header){
int num = 0;
while(header!=null){
num++;
header = header.next;
}
return num;
}
/**
* 從尾到頭打印鏈表
* 建棧
*/
public void reversePrintLink(Node node){
Stack<Node> stack = new Stack<Node>();
while(node!=null){
stack.push(node);
node = node.next;
}
while(!stack.isEmpty()){
System.out.print(stack.pop().data+" ");
}
System.out.println();
}
/**
* 從尾到頭打印鏈表
* 遞歸
*/
public void reversePrintLink1(Node node){
if(node!=null){
reversePrintLink1(node.next);
System.out.print(node.data+" ");
}
}
/**
* 正序打印
*/
public void printLink(Node node){
while(node!=null){
System.out.print(node.data+" ");
node = node.next;
}
}
/**
* 反轉(zhuǎn)鏈表
*/
public void reverseLink(){
Node curNode = header;
Node preNode = null;
Node nextNode = null;
while(curNode!=null){
nextNode = curNode.next;//保留下一個(gè)節(jié)點(diǎn)（因?yàn)橐獢嚅_下面了）
curNode.next = preNode;//反轉(zhuǎn)指針到前面
//移動(dòng)節(jié)點(diǎn)為了繼續(xù)下一次保存、斷開虚茶、反轉(zhuǎn)
preNode = curNode;
curNode = nextNode;
}
header = preNode;
}
/**
* 創(chuàng)建有環(huán)鏈表只為測(cè)試用
*/
public void createRing(){
header = new Node(1);
header.next = header;
}
/**
* 是否有環(huán)
* 設(shè)置快指針和慢指針戈鲁，慢指針每次走一步，快指針每次走兩步
* 當(dāng)快指針與慢指針相等時(shí)嘹叫，就說明該鏈表有環(huán)
*/
public boolean isRing(){
if(header == null){
return false;
}
Node slow = header;
Node fast = header;
if(fast.next!=null && fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
/**
* 創(chuàng)建添加節(jié)點(diǎn)的鏈表方法婆殿，為測(cè)試相交
*/
public void add(Node node){
if(node==null){
return;
}
if(header==null){
header = node;
}else{
node.next = header;
header = node;
}
}
/**
* 兩個(gè)鏈表是否相交
* 兩個(gè)鏈表相交，則它們的尾結(jié)點(diǎn)一定相同罩扇，比較兩個(gè)鏈表的尾結(jié)點(diǎn)是否相同即可
*/
public static boolean isCross(Node head1,Node head2){
if(head1==null||head2==null){
return false;
}
Node temp1 = head1;
Node temp2 = head2;
while(temp1.next!=null){
temp1 = temp1.next;
}
while(temp2.next!=null){
temp2 = temp2.next;
}
return temp1 == temp2;
}
/**
* 如果鏈表相交婆芦，求鏈表相交的起始點(diǎn)：
* 1、首先判斷鏈表是否相交喂饥，如果兩個(gè)鏈表不相交消约，則求相交起點(diǎn)沒有意義
* 2、求出兩個(gè)鏈表長(zhǎng)度之差：len=length1-length2
* 3员帮、讓較長(zhǎng)的鏈表先走len步
* 4或粮、然后兩個(gè)鏈表同步向前移動(dòng)，沒移動(dòng)一次就比較它們的結(jié)點(diǎn)是否相等捞高，第一個(gè)相等的結(jié)點(diǎn)即為它們的第一個(gè)相交點(diǎn)
*/
public static Node findFirstCrossPoint(LinkList linkedList1, LinkList linkedList2){
//鏈表不相交
if(!isCross(linkedList1.header,linkedList2.header)){
return null;
}else{
int length1 = linkedList1.getLength(linkedList1.header);//鏈表1的長(zhǎng)度
int length2 = linkedList2.getLength(linkedList2.header);//鏈表2的長(zhǎng)度
Node temp1 = linkedList1.header;//鏈表1的頭結(jié)點(diǎn)
Node temp2 = linkedList2.header;//鏈表2的頭結(jié)點(diǎn)
int len = length1 - length2;//鏈表1和鏈表2的長(zhǎng)度差
if(len > 0){//鏈表1比鏈表2長(zhǎng)被啼，鏈表1先前移len步
for(int i=0; i<len; i++){
temp1 = temp1.next;
}
}else{//鏈表2比鏈表1長(zhǎng)，鏈表2先前移len步
for(int i=0; i<-len; i++){
temp2 = temp2.next;
}
}
//鏈表1和鏈表2同時(shí)前移,直到找到鏈表1和鏈表2相交的結(jié)點(diǎn)
while(temp1 != temp2){
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp1;
}
}
/**
* 查找單鏈表中第K個(gè)節(jié)點(diǎn)
* 第二種解法是快慢指針,主要思路就是使用兩個(gè)指針棠枉，先讓前面的指針走到正向第k個(gè)結(jié)點(diǎn)，
* 后面的指針才走泡挺，這樣前后兩個(gè)指針的距離差是k-1辈讶，之后前后兩個(gè)指針一起向前走，
* 前面的指針走到最后一個(gè)結(jié)點(diǎn)時(shí)娄猫，后面指針?biāo)附Y(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn)
*/
public Node getKNode(Node head,int k){
if(k<0||k>getLength(header)){
return null;
}
Node first = head;
Node last = head;
for(int i=1;i<k;i++){
first = first.next;
}
while(first.next!=null){
first = first.next;
last = last.next;
}
return last;
}
/**
* 尋找單鏈表的中間結(jié)點(diǎn)：
* 方法一贱除、先求出鏈表的長(zhǎng)度，再遍歷1/2鏈表長(zhǎng)度媳溺，尋找出鏈表的中間結(jié)點(diǎn)
* 方法二月幌、：
* 用兩個(gè)指針遍歷鏈表，一個(gè)快指針悬蔽、一個(gè)慢指針扯躺，
* 快指針每次向前移動(dòng)2個(gè)結(jié)點(diǎn)，慢指針一次向前移動(dòng)一個(gè)結(jié)點(diǎn)，
* 當(dāng)快指針移動(dòng)到鏈表的末尾录语，慢指針?biāo)诘奈恢眉礊橹虚g結(jié)點(diǎn)所在的位置
*/
public Node findMiddleNode(){
Node slowPoint = header;
Node quickPoint = header;
//鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí),返回的是中間結(jié)點(diǎn)倍啥；鏈表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，返回的是中間兩個(gè)結(jié)點(diǎn)中的前一個(gè)
while(quickPoint.next != null && quickPoint.next.next != null){
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint;
}
}
測(cè)試代碼如下：
public class LinkTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
//測(cè)試尾插法和遞歸從尾達(dá)到頭打印
System.out.println("---------測(cè)試尾插法和遞歸打印----------");
LinkList mLink = new LinkList();
mLink.addNodeEnd(1);
mLink.addNodeEnd(2);
mLink.addNodeEnd(3);
System.out.println(mLink.getLength(mLink.header));
mLink.reversePrintLink1(mLink.header);
System.out.println();
//測(cè)試頭插法和棧從尾達(dá)到頭打印
System.out.println("---------測(cè)試頭插法和棧打印----------");
LinkList mLink1 = new LinkList();
mLink1.addNodeHead(1);
mLink1.addNodeHead(2);
mLink1.addNodeHead(3);
mLink1.addNodeHead(4);
System.out.println(mLink1.getLength(mLink1.header));
mLink1.reversePrintLink(mLink1.header);
System.out.println();
//測(cè)試反轉(zhuǎn)
System.out.println("---------測(cè)試反轉(zhuǎn)----------");
LinkList mLink2 = new LinkList();
mLink2.addNodeEnd(5);
mLink2.addNodeEnd(6);
mLink2.addNodeEnd(7);
mLink2.addNodeEnd(8);
mLink2.reverseLink();
mLink2.printLink(mLink2.header);
System.out.println();
//測(cè)試有環(huán)
System.out.println("---------測(cè)試有環(huán)----------");
LinkList mLink3 = new LinkList();
mLink3.createRing();
System.out.println("是否有環(huán)："+mLink3.isRing());
System.out.println("---------測(cè)試相交----------");
LinkList mLink4 = new LinkList();
LinkList mLink5 = new LinkList();
LinkList.Node node = new LinkList.Node(0);
mLink4.addNodeHead(1);
mLink5.addNodeHead(1);
mLink4.add(node);
mLink5.add(node);
mLink5.addNodeHead(2);
System.out.println("是否相交："+LinkList.isCross(mLink4.header,mLink5.header));
System.out.println("相交的起始節(jié)點(diǎn)："+LinkList.findFirstCrossPoint(mLink4, mLink5).data);
System.out.println("---------測(cè)試返回倒數(shù)第k個(gè)節(jié)點(diǎn)----------");
LinkList mLink6 = new LinkList();
mLink6.addNodeEnd(1);
mLink6.addNodeEnd(2);
mLink6.addNodeEnd(3);
mLink6.addNodeEnd(4);
mLink6.addNodeEnd(5);
mLink6.addNodeEnd(6);
System.out.println(mLink6.getKNode(mLink6.header, 2).data);
}
}
打印如下：
---------測(cè)試尾插法和遞歸打印----------
3
3 2 1
---------測(cè)試頭插法和棧打印----------
4
1 2 3 4
---------測(cè)試反轉(zhuǎn)----------
8 7 6 5
---------測(cè)試有環(huán)----------
是否有環(huán)：true
---------測(cè)試相交----------
是否相交：true
相交的起始節(jié)點(diǎn)：0
---------測(cè)試尾插法和遞歸打印----------
5
相關(guān)博文：
java實(shí)現(xiàn)單鏈表常見操作 ----方法思路標(biāo)注詳細(xì)
面試中的Java鏈表---這個(gè)是一個(gè)面試題一個(gè)解
http://www.reibang.com/p/6ebedde370b0
