單鏈表結構：

Java中單鏈表採用Node實體類類標識，其中data為儲存的資料，next為下一個節點的指標：

package com.algorithm.link;

/**

* 連結串列結點的實體類

*

*/

public class Node {

Node next = null;//下一個結點

int data;//結點資料

public Node(int data){

this.data = data;

}

}

連結串列常見操作：

package com.algorithm.link;

import java.util.Hashtable;

/**

* 單鏈表常見演算法

*

*/

public class MyLinkedList {

/**連結串列的頭結點*/

Node head = null;

/**

* 連結串列新增結點:

* 找到連結串列的末尾結點，把新新增的資料作為末尾結點的後續結點

* @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;

}

/**

* @param index

* @return

*/

public boolean deleteNode(int index){

return false;

}

head = head.next;

return true;

}

Node preNode = head;

Node curNode = preNode.next;

int i = 1;

while(curNode != null){

return true;

}

//當先結點和前結點同時向後移

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;

}

/**

* 連結串列結點排序,並返回排序後的頭結點:

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

* @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;

}

/**

* 列印結點

*/

public void printLink(){

Node curNode = head;

while(curNode !=null){

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

curNode = curNode.next;

}

System.out.println();

}

/**

* 去掉重複元素:

* 需要額外的儲存空間hashtable，呼叫hashtable.containsKey()來判斷重複結點

*/

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中已存在該結點，則跳過該結點

pre.next = temp.next;

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

hb.put(temp.data, 1);

pre=temp;

}

temp = temp.next;

}

}

/**

* 返回倒數第k個結點,

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

* 當前面的指標到達末尾時，後面的指標所在的位置就是倒數第k個位置

* @param k

* @return

*/

public Node findReverNode(int k){

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

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;

}

/**

* 查詢正數第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;

}

/**

* 反轉連結串列，在反轉指標錢一定要儲存下個結點的指標

*/

public void reserveLink(){

Node curNode = head;//頭結點

Node preNode = null;//前一個結點

while(curNode != null){

Node nextNode = curNode.next;//保留下一個結點

curNode.next = preNode;//指標反轉

preNode = curNode;//前結點後移

curNode = nextNode;//當前結點後移

}

head = preNode;

}

/**

* 反向輸出連結串列，三種方式：

* 方法一、先反轉連結串列，再輸出連結串列，需要連結串列遍歷兩次

* 方法二、把連結串列中的數字放入棧中再輸出，需要維護額外的棧空間

* 方法三、依據方法2中棧的思想，透過遞迴來實現，遞迴起始就是將先執行的資料壓入棧中，再一次出棧

*/

public void reservePrt(Node node){

if(node != null){

reservePrt(node.next);

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

}

}

/**

* 尋找單鏈表的中間結點：

* 方法一、先求出連結串列的長度，再遍歷1/2連結串列長度，尋找出連結串列的中間結點

* 方法二、：

* 用兩個指標遍歷連結串列，一個快指標、一個慢指標，

* 快指標每次向前移動2個結點，慢指標一次向前移動一個結點，

* 當快指標移動到連結串列的末尾，慢指標所在的位置即為中間結點所在的位置

*/

public Node findMiddleNode(){

Node slowPoint = head;

Node quickPoint = head;

//quickPoint.next == null是連結串列結點個數為奇數時，快指標已經走到最後了

//quickPoint.next.next == null是連結串列結點數為偶數時，快指標已經走到倒數第二個結點了

//連結串列結點個數為奇數時,返回的是中間結點；連結串列結點個數為偶數時，返回的是中間兩個結點中的前一個

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

slowPoint = slowPoint.next;

quickPoint = quickPoint.next.next;

}

return slowPoint;

}

/**

* 判斷連結串列是否有環：

* 設定快指標和慢指標，慢指標每次走一步，快指標每次走兩步

* 當快指標與慢指標相等時，就說明該連結串列有環

*/

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;

}

/**

* 返回連結串列的最後一個結點

*/

public Node getLastNode(){

Node temp = head;

while(temp.next != null){

temp = temp.next;

}

return temp;

}

/**

*/

public boolean deleteSpecialNode(Node n){

if(n.next == null){

return false;

}else{

//交換結點和其後續結點中的資料

int temp = n.data;

n.data = n.next.data;

n.next.data = temp;

n.next = n.next.next;

return true;

}

}

/**

* 判斷兩個連結串列是否相交：

* 兩個連結串列相交，則它們的尾結點一定相同，比較兩個連結串列的尾結點是否相同即可

*/

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、然後兩個連結串列同步向前移動，沒移動一次就比較它們的結點是否相等，第一個相等的結點即為它們的第一個相交點

*/

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的頭結點

Node temp2 = linkedList2.head;//連結串列2的頭結點

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相交的結點

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();

//新增連結串列結點

myLinkedList.addNode(9);

myLinkedList.addNode(8);

myLinkedList.addNode(6);

myLinkedList.addNode(3);

myLinkedList.addNode(5);

//列印連結串列

myLinkedList.printLink();

/*//測試連結串列結點個數

System.out.println("連結串列結點個數為：" + myLinkedList.length());

//連結串列排序

Node head = myLinkedList.linkSort();

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

myLinkedList.printLink();

//去除重複結點

myLinkedList.distinctLink();

myLinkedList.printLink();

//連結串列反轉

myLinkedList.reserveLink();

myLinkedList.printLink();

//倒序輸出/遍歷連結串列

myLinkedList.reservePrt(myLinkedList.head);

//返回連結串列的中間結點

Node middleNode = myLinkedList.findMiddleNode();

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

//判斷連結串列是否有環

boolean isRinged = myLinkedList.isRinged();

System.out.println("連結串列是否有環：" + isRinged);

//將連結串列的最後一個結點指向頭結點，製造有環的效果

Node lastNode = myLinkedList.getLastNode();

lastNode.next = myLinkedList.head;

isRinged = myLinkedList.isRinged();

System.out.println("連結串列是否有環：" + isRinged);

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));

//把第二個連結串列從第三個結點開始接在第二個連結串列的後面，製造相交的效果

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

myLinkedList1.printLink();

System.out.println("連結串列一和連結串列二是否相交"+myLinkedList.isCross(myLinkedList.head, myLinkedList1.head));

*/

//如果兩個連結串列相交求連結串列相交的結點的值

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("兩個連結串列相交，第一個交點的數值為：" + n.data);

}

}

}