链表的增加、删除、删除重复数据、找出链表中倒数第K个元素、链表的反转、从头到尾输出单链表、找到链表的中间节点、检测链表是否有环、找到链表的如口、求环的长度。在不知道头节点的情况下删除指定节点，判断两个链表是否相交，找到相交的第一个节点。
public class MyLinkedList {
Node head = null;
/**
* 向链表中插入数据
*
* @param d
* :插入数据的内容
*/
public void addNode(int d) {
Node newNode = new Node(d);
if (head == null) {
head = newNode;
return;
}
Node tmp = head;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = newNode;
}
/**
* @return 返回节点的长度
*/
public int length() {
int length = 0;
Node tmp = head;
while (tmp.next != null) {
length++;
tmp = tmp.next;
}
return length;
}
/**
* @param index:删除第index个节点
* @return 成功返回true,失败返回false
*/
public Boolean deleteNode(int index) {
if (index < 1 || index > length())
return false;
if (index == 1) {
head = head.next;
return true;
}
int i = 1;
Node preNode = head;
Node curNode = preNode.next;
while (curNode != null) {
if (i == index) {
preNode.next = curNode.next;
return true;
}
preNode = curNode;
curNode = curNode.next;
i++;
}
return true;
}
/**
* 对链表进行排序（简单选择排序）
*
* @return 返回排序后的头结点
*/
public Node orderList() {
Node nextNode = null;
int temp = 0;
Node curNode = head;
while (curNode.next != null) {
nextNode = curNode.next;
while (nextNode != null) {
if (curNode.data > nextNode.data) {
temp = curNode.data;
curNode.data = nextNode.data;
nextNode.data = temp;
}
nextNode = nextNode.next;
}
curNode = curNode.next;
}
return head;
}
public void printList() {
Node tmp = head;
while (tmp != null) {
System.out.println(tmp.data);
tmp = tmp.next;
}
}
/**
* 删除重复数据
*/
public void deleteDuplecate(Node head) {
Node p = head;
while (p != null) {
Node q = p;
while (q.next != null) {
if (p.data == q.next.data) {
q.next = q.next.next;
} else {
q = q.next;
}
}
p = p.next;
}
}
/**
* 找出单链表中倒数第K个元素
*/
public Node findElem(Node head, int k) {
if (k < 1 || k > this.length()) {
return null;
}
Node p1 = head;
Node p2 = head;
for (int i = 0; i < k - 1; i++) {
p1 = p1.next;
}
while (p1.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
/**
* 链表的反转
*/
public void ReverseIteratively(Node head) {
Node pReversedIteratively = head;
Node pNode = head;
Node pPrev = null;
while (pNode != null) {
Node pNext = pNode.next;
if (pNext == null) {
pReversedIteratively = pNode;
}
pNode.next = pPrev;
pPrev = pNode;
pNode = pNext;
}
this.head = pReversedIteratively;
}
/**
* 从尾到头输出单链表
*/
public void printListReversely(Node pListNode) {
if (pListNode != null) {
printListReversely(pListNode.next);
System.out.println(pListNode.data);
}
}
/**
* 寻找单链表的中间节点
*
*/
public Node SearchMid(Node head){
Node p = this.head;
Node q = this.head;
while(p!=null && p.next!=null && p.next.next!=null){
p=p.next .next;
q=q.next;
}
return q;
}
/**
* 检测一个链表是否有环
*/
public boolean IsLoop(Node head){
Node fast = head;
Node slow= head;
if(fast==null){
return false;
}
while(fast.next!=null&& fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return true;
}
}
return !(fast==null||fast.next==null);
}
/**
* 找到环的入口
*/
public Node FindLoopPort(Node head){
Node slow = head;
Node fast = head;
while(fast.next!=null&& fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
break;
}
}
if(fast==null||fast.next==null)
return null;
slow = head;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}
/**
*
* 计算环的长度
*/
public int LoopLength(Node head){
Node fast = head;
Node slow= head;
if(fast==null){
return 0;
}
int length=0;
boolean second = false;
boolean begin =false;
while(fast.next!=null&& fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow && second==false){
second=true;
begin=true;
}
if(begin==true){
length++;
}
if(fast==slow && second==true){
break;
}
}
return length;
}
/**
* 在不知道头指针的情况下删除制定节点
* 1、若待删除的节点为链表尾节点，则无法删除，因为删除后部分使其前驱节点的next指针位空
* 2、若待删除的节点不是尾节点，则通过交换这个节点与其后继节点的值，然后删除后继节点。
*/
public boolean deleteNode(Node n){
if (n==null||n.next==null){
return false;
}
int tmp= n.data;
n.data=n.next.data;
n.next.data=tmp;
n.next=n.next.next;
return true;
}
/**
* 如何判断两个链表是否相交
*/
public boolean isIntersect(Node h1,Node h2){
if(h1==null||h2==null){
return false;
}
Node tail1 = h1;
while(tail1.next!= null){
tail1=tail1.next;
}
Node tail2 = h2;
while(tail2.next!= null){
tail2=tail2.next;
}
return tail1==tail2;
}
/**
* 如果链表相交，如何找到它们相交的第一个节点
*/
public Node getFirstMeetNode(Node h1,Node h2){
if(h1==null||h2==null){
return null;
}
Node tail1 = h1;
int len1 = 1;
while(tail1.next!= null){
tail1=tail1.next;
len1++;
}
Node tail2 = h2;
int len2=1;
while(tail2.next!= null){
tail2=tail2.next;
len2++;
}
if(tail1!=tail2)
return null;
Node t1= h1;
Node t2 = h2;
if(len1>len2){
int d= len1-len2;
while(d!=0){
t1=t1.next;
d--;
}
}
else{
int d= len2-len1;
while(d!=0){
t2=t2.next;
d--;
}
}
while(t1!=t2){
t1=t1.next;
t2=t2.next;
}
return t1;
}
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.addNode(5);
list.addNode(3);
list.addNode(1);
list.addNode(3);
list.addNode(4);
System.out.println("List length = " + list.length());
System.out.println("before order:");
list.printList();
list.orderList();
System.out.println("after order:");
list.printList();
System.out.println("after delete duplecate:");
list.deleteDuplecate(list.head);
list.printList();
System.out.println("K Elem");
Node Knode = list.findElem(list.head, 3);
while (Knode != null) {
System.out.println(Knode.data);
Knode = Knode.next;
}
System.out.println("Before Reverse List: ");
list.printList();
System.out.println("After Reverse List: ");
list.ReverseIteratively(list.head);
list.printList();
System.out.println(" Print List: ");
list.printList();
System.out.println(" Reverse Print List: ");
list.printListReversely(list.head);
}
}
class Node {
Node next = null;
int data;
public Node(int data) {
this.data = data;
}
}版权声明：本文为m0_37744293原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。