如何使用Java實現(xiàn)單鏈表？

單鏈表結(jié)構(gòu)：

Java中單鏈表采用node實體類類標識，其中data為存儲的數(shù)據(jù)，next為下一個節(jié)點的指針：

package com.algorithm.link;

/**

* 鏈表結(jié)點的實體類

*

*/

public class Node {

Node next = null;//下一個結(jié)點

int data;//結(jié)點數(shù)據(jù)

public Node(int data){

this.data = data;

}

}

鏈表常見操作：

package com.algorithm.link;

import java.util.hashtable;

/**

* 單鏈表常見算法

*

*/

public class MyLinkedList {

/**鏈表的頭結(jié)點*/

Node head = null;

/**

* 鏈表添加結(jié)點:

* 找到鏈表的末尾結(jié)點，把新添加的數(shù)據(jù)作為末尾結(jié)點的后續(xù)結(jié)點

* @param data

*/

public void addNode(int data){

Node newNode = new Node(data);

if(head == null){

head = newNode;

return;

}

Node temp = head;

while(temp.next != null){

temp = temp.next;

}

temp.next = newNode;

}

/**

* 鏈表刪除結(jié)點:

* 把要刪除結(jié)點的前結(jié)點指向要刪除結(jié)點的后結(jié)點，即直接跳過待刪除結(jié)點

* @param index

* @return

*/

public boolean deleteNode(int index){

if(index<1 || index>length()){//待刪除結(jié)點不存在

return false;

}

if(index == 1){//刪除頭結(jié)點

head = head.next;

return true;

}

Node preNode = head;

Node curNode = preNode.next;

int i = 1;

while(curNode != null){

if(i==index){//尋找到待刪除結(jié)點

preNode.next = curNode.next;//待刪除結(jié)點的前結(jié)點指向待刪除結(jié)點的后結(jié)點

return true;

}

//當先結(jié)點和前結(jié)點同時向后移

preNode = preNode.next;

curNode = curNode.next;

i++;

}

return true;

}

/**

* 求鏈表的長度

* @return

*/

public int length(){

int length = 0;

Node curNode = head;

while(curNode != null){

length++;

curNode = curNode.next;

}

return length;

}

/**

* 鏈表結(jié)點排序,并返回排序后的頭結(jié)點:

* 選擇排序算法,即每次都選出未排序結(jié)點中最小的結(jié)點，與第一個未排序結(jié)點交換

* @return

*/

public Node linkSort(){

Node curNode = head;

while(curNode != null){

Node nextNode = curNode.next;

while(nextNode != null){

if(curNode.data > nextNode.data){

int temp = curNode.data;

curNode.data = nextNode.data;

nextNode.data = temp;

}

nextNode = nextNode.next;

}

curNode = curNode.next;

}

return head;

}

/**

* 打印結(jié)點

*/

public void printLink(){

Node curNode = head;

while(curNode !=null){

System.out.print(curNode.data+" ");

curNode = curNode.next;

}

System.out.println();

}

/**

* 去掉重復元素:

* 需要額外的存儲空間hashtable，調(diào)用hashtable.containsKey()來判斷重復結(jié)點

*/

public void distinctLink(){

Node temp = head;

Node pre = null;

Hashtable<Integer, Integer> hb = new Hashtable<Integer, Integer>();

while(temp != null){

if(hb.containsKey(temp.data)){//如果hashtable中已存在該結(jié)點，則跳過該結(jié)點

pre.next = temp.next;

}else{//如果hashtable中不存在該結(jié)點，將結(jié)點存到hashtable中

hb.put(temp.data, 1);

pre=temp;

}

temp = temp.next;

}

}

/**

* 返回倒數(shù)第k個結(jié)點,

* 兩個指針，第一個指針向前移動k-1次，之后兩個指針共同前進，

* 當前面的指針到達末尾時，后面的指針所在的位置就是倒數(shù)第k個位置

* @param k

* @return

*/

public Node findReverNode(int k){

if(k<1 || k>length()){//第k個結(jié)點不存在

return null;

}

Node first = head;

Node second = head;

for(int i=0; i<k-1; i++){//前移k-1步

first = first.next;

}

while(first.next != null){

first = first.next;

second = second.next;

}

return second;

}

/**

* 查找正數(shù)第k個元素

*/

public Node findNode(int k){

if(k<1 || k>length()){//不合法的k

return null;

}

Node temp = head;

for(int i = 0; i<k-1; i++){

temp = temp.next;

}

return temp;

}

/**

* 反轉(zhuǎn)鏈表，在反轉(zhuǎn)指針錢一定要保存下個結(jié)點的指針

*/

public void reserveLink(){

Node curNode = head;//頭結(jié)點

Node preNode = null;//前一個結(jié)點

while(curNode != null){

Node nextNode = curNode.next;//保留下一個結(jié)點

curNode.next = preNode;//指針反轉(zhuǎn)

preNode = curNode;//前結(jié)點后移

curNode = nextNode;//當前結(jié)點后移

}

head = preNode;

}

/**

* 反向輸出鏈表，三種方式：

* 方法一、先反轉(zhuǎn)鏈表，再輸出鏈表，需要鏈表遍歷兩次

* 方法二、把鏈表中的數(shù)字放入棧中再輸出，需要維護額外的棧空間

* 方法三、依據(jù)方法2中棧的思想，通過遞歸來實現(xiàn)，遞歸起始就是將先執(zhí)行的數(shù)據(jù)壓入棧中，再一次出棧

*/

public void reservePrt(Node node){

if(node != null){

reservePrt(node.next);

System.out.print(node.data+" ");

}

}

/**

* 尋找單鏈表的中間結(jié)點：

* 方法一、先求出鏈表的長度，再遍歷1/2鏈表長度，尋找出鏈表的中間結(jié)點

* 方法二、：

* 用兩個指針遍歷鏈表，一個快指針、一個慢指針，

* 快指針每次向前移動2個結(jié)點，慢指針一次向前移動一個結(jié)點，

* 當快指針移動到鏈表的末尾，慢指針所在的位置即為中間結(jié)點所在的位置

*/

public Node findMiddlenode(){

Node slowPoint = head;

Node quickPoint = head;

//quickPoint.next == null是鏈表結(jié)點個數(shù)為奇數(shù)時，快指針已經(jīng)走到最后了

//quickPoint.next.next == null是鏈表結(jié)點數(shù)為偶數(shù)時，快指針已經(jīng)走到倒數(shù)第二個結(jié)點了

//鏈表結(jié)點個數(shù)為奇數(shù)時,返回的是中間結(jié)點；鏈表結(jié)點個數(shù)為偶數(shù)時，返回的是中間兩個結(jié)點中的前一個

while(quickPoint.next != null && quickPoint.next.next != null){

slowPoint = slowPoint.next;

quickPoint = quickPoint.next.next;

}

return slowPoint;

}

/**

* 判斷鏈表是否有環(huán)：

* 設(shè)置快指針和慢指針，慢指針每次走一步，快指針每次走兩步

* 當快指針與慢指針相等時，就說明該鏈表有環(huán)

*/

public boolean isRinged(){

if(head == null){

return false;

}

Node slow = head;

Node fast = head;

while(fast.next != null && fast.next.next != null){

slow = slow.next;

fast = fast.next.next;

if(fast == slow){

return true;

}

}

return false;

}

/**

* 返回鏈表的最后一個結(jié)點

*/

public Node getLastNode(){

Node temp = head;

while(temp.next != null){

temp = temp.next;

}

return temp;

}

/**

* 在不知道頭結(jié)點的情況下刪除指定結(jié)點：

* 刪除結(jié)點的重點在于找出其前結(jié)點，使其前結(jié)點的指針指向其后結(jié)點，即跳過待刪除結(jié)點

* 1、如果待刪除的結(jié)點是尾結(jié)點，由于單鏈表不知道其前結(jié)點，沒有辦法刪除

* 2、如果刪除的結(jié)點不是尾結(jié)點，則將其該結(jié)點的值與下一結(jié)點交換，然后該結(jié)點的指針指向下一結(jié)點的后續(xù)結(jié)點

*/

public boolean deleteSpecialNode(Node n){

if(n.next == null){

return false;

}else{

//交換結(jié)點和其后續(xù)結(jié)點中的數(shù)據(jù)

int temp = n.data;

n.data = n.next.data;

n.next.data = temp;

//刪除后續(xù)結(jié)點

n.next = n.next.next;

return true;

}

}

/**

* 判斷兩個鏈表是否相交：

* 兩個鏈表相交，則它們的尾結(jié)點一定相同，比較兩個鏈表的尾結(jié)點是否相同即可

*/

public boolean isCross(Node head1, Node head2){

Node temp1 = head1;

Node temp2 = head2;

while(temp1.next != null){

temp1 = temp1.next;

}

while(temp2.next != null){

temp2 = temp2.next;

}

if(temp1 == temp2){

return true;

}

return false;

}

/**

* 如果鏈表相交，求鏈表相交的起始點：

* 1、首先判斷鏈表是否相交，如果兩個鏈表不相交，則求相交起點沒有意義

* 2、求出兩個鏈表長度之差：len=length1-length2

* 3、讓較長的鏈表先走len步

* 4、然后兩個鏈表同步向前移動，沒移動一次就比較它們的結(jié)點是否相等，第一個相等的結(jié)點即為它們的第一個相交點

*/

public Node findFirstCrossPoint(MyLinkedList linkedList1, MyLinkedList linkedList2){

//鏈表不相交

if(!isCross(linkedList1.head,linkedList2.head)){

return null;

}else{

int length1 = linkedList1.length();//鏈表1的長度

int length2 = linkedList2.length();//鏈表2的長度

Node temp1 = linkedList1.head;//鏈表1的頭結(jié)點

Node temp2 = linkedList2.head;//鏈表2的頭結(jié)點

int len = length1 - length2;//鏈表1和鏈表2的長度差

if(len > 0){//鏈表1比鏈表2長，鏈表1先前移len步

for(int i=0; i<len; i++){

temp1 = temp1.next;

}

}else{//鏈表2比鏈表1長，鏈表2先前移len步

for(int i=0; i<len; i++){

temp2 = temp2.next;

}

}

//鏈表1和鏈表2同時前移,直到找到鏈表1和鏈表2相交的結(jié)點

while(temp1 != temp2){

temp1 = temp1.next;

temp2 = temp2.next;

}

return temp1;

}

}

}

測試類：

package com.algorithm.link;

/**

* 單鏈表操作測試類

* @author bjh

*

*/

public class Test {

public static void main(String[] args){

MyLinkedList myLinkedList = new MyLinkedList();

//添加鏈表結(jié)點

myLinkedList.addNode(9);

myLinkedList.addNode(8);

myLinkedList.addNode(6);

myLinkedList.addNode(3);

myLinkedList.addNode(5);

//打印鏈表

myLinkedList.printLink();

/*//測試鏈表結(jié)點個數(shù)

System.out.println("鏈表結(jié)點個數(shù)為：" + myLinkedList.length());

//鏈表排序

Node head = myLinkedList.linkSort();

System.out.println("排序后的頭結(jié)點為：" + head.data);

myLinkedList.printLink();

//去除重復結(jié)點

myLinkedList.distinctLink();

myLinkedList.printLink();

//鏈表反轉(zhuǎn)

myLinkedList.reserveLink();

myLinkedList.printLink();

//倒序輸出/遍歷鏈表

myLinkedList.reservePrt(myLinkedList.head);

//返回鏈表的中間結(jié)點

Node middleNode = myLinkedList.findMiddleNode();

System.out.println("中間結(jié)點的數(shù)值為："+middleNode.data);

//判斷鏈表是否有環(huán)

boolean isRinged = myLinkedList.isRinged();

System.out.println("鏈表是否有環(huán)：" + isRinged);

//將鏈表的最后一個結(jié)點指向頭結(jié)點，制造有環(huán)的效果

Node lastNode = myLinkedList.getLastNode();

lastNode.next = myLinkedList.head;

isRinged = myLinkedList.isRinged();

System.out.println("鏈表是否有環(huán)：" + isRinged);

//刪除指定結(jié)點

Node nk = myLinkedList.findReverNode(3);

System.out.println(nk.data);

myLinkedList.deleteSpecialNode(nk);

myLinkedList.printLink();

//鏈表是否相交

//新鏈表

MyLinkedList myLinkedList1 = new MyLinkedList();

myLinkedList1.addNode(1);

myLinkedList1.addNode(2);

myLinkedList1.printLink();

System.out.println("鏈表一和鏈表二是否相交"+myLinkedList.isCross(myLinkedList.head, myLinkedList1.head));

//把第二個鏈表從第三個結(jié)點開始接在第二個鏈表的后面，制造相交的效果

myLinkedList1.findNode(2).next = myLinkedList.findNode(3);

myLinkedList1.printLink();

System.out.println("鏈表一和鏈表二是否相交"+myLinkedList.isCross(myLinkedList.head, myLinkedList1.head));

*/

//如果兩個鏈表相交求鏈表相交的結(jié)點的值

MyLinkedList myLinkedList1 = new MyLinkedList();

myLinkedList1.addNode(1);

myLinkedList1.addNode(2);

myLinkedList1.findNode(2).next = myLinkedList.findNode(3);

myLinkedList1.printLink();

Node n = myLinkedList1.findFirstCrossPoint(myLinkedList, myLinkedList1);

if(n == null){

System.out.println("鏈表不相交");

}else{

System.out.println("兩個鏈表相交，第一個交點的數(shù)值為：" + n.data);

}

}

}