import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;
/**
*
* @author kerryfish
* 关于java中链表的操作
* 1. 求单链表中结点的个数: getListLength
* 2. 将单链表反转: reverseList(遍历),reverseListRec(递归)
* 3. 查找单链表中的倒数第K个结点(k > 0): reGetKthNode
* 4. 查找单链表的中间结点: getMiddleNode
* 5. 从尾到头打印单链表: reversePrintListStack,reversePrintListRec(递归)
* 6. 已知两个单链表pHead1 和pHead2 各自有序,把它们合并成一个链表依然有序: mergeSortedList, mergeSortedListRec
* 7. 对单链表进行排序,listSort(归并),insertionSortList(插入)
* 8. 判断一个单链表中是否有环: hasCycle
* 9. 判断两个单链表是否相交: isIntersect
* 10. 已知一个单链表中存在环,求进入环中的第一个节点: getFirstNodeInCycle, getFirstNodeInCycleHashMap
* 11. 给出一单链表头指针head和一节点指针delete,O(1)时间复杂度删除节点delete: deleteNode
*/
public class LinkedListSummary {
/**
* @param args
*
*/
public static class Node{
int value;
Node next;
public Node(int n){
this.value=n;
this.next=null;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
Node head=null;
if(in.hasNextInt()){
head=new Node(in.nextInt());
}
Node temp=head;
while(in.hasNextInt()){
temp.next=new Node(in.nextInt());
temp=temp.next;
}
in.close();
//int len=getListLength(head);
//Node reHead=reverseList(head);
//reHead=reverseListRec(reHead);
//Node node_k=reGetKthNode(head,3);
//Node mid=getMiddleNode(head);
//reversePrintListRec(head);
//reversePrintListStack(head);
//Node mergeHead=mergeSortedList(head,null);
//Node sortHead=listSort(head);
}
//求单链表中结点的个数: getListLength
public static int getListLength(Node head){
int len=0;
while(head!=null){
len++;
head=head.next;
}
return len;
}
//将单链表反转,循环
public static Node reverseList(Node head){
if(head==null||head.next==null)return head;
Node pre=null;
Node nex=null;
while(head!=null){
nex=head.next;
head.next=pre;
pre=head;
head=nex;
}
return pre;
}
//将单链表反转,递归
public static Node reverseListRec(Node head){
if(head==null||head.next==null)return head;
Node reHead=reverseListRec(head.next);
head.next.next=head;
head.next=null;
return reHead;
}
//查找单链表中的倒数第K个结点(k > 0)
public static Node reGetKthNode(Node head,int k){
if(head==null)return head;
int len=getListLength(head);
if(k>len)return null;
Node target=head;
Node nexk=head;
for(int i=0;i<k;i++){
nexk=nexk.next;
}
while(nexk!=null){
target=target.next;
nexk=nexk.next;
}
return target;
}
//查找单链表的中间结点
public static Node getMiddleNode(Node head){
if(head==null||head.next==null)return head;
Node target=head;
Node temp=head;
while(temp!=null&&temp.next!=null){
target=target.next;
temp=temp.next.next;
}
return target;
}
//从尾到头打印单链表,递归
public static void reversePrintListRec(Node head){
if(head==null)return;
else{
reversePrintListRec(head.next);
System.out.println(head.value);
}
}
//从尾到头打印单链表,栈
public static void reversePrintListStack(Node head){
Stack<Node> s=new Stack<Node>();
while(head!=null){
s.push(head);
head=head.next;
}
while(!s.isEmpty()){
System.out.println(s.pop().value);
}
}
//合并两个有序的单链表head1和head2,循环
public static Node mergeSortedList(Node head1,Node head2){
if(head1==null)return head2;
if(head2==null)return head1;
Node target=null;
if(head1.value>head2.value){
target=head2;
head2=head2.next;
}
else{
target=head1;
head1=head1.next;
}
target.next=null;
Node mergeHead=target;
while(head1!=null && head2!=null){
if(head1.value>head2.value){
target.next=head2;
head2=head2.next;
}
else{
target.next=head1;
head1=head1.next;
}
target=target.next;
target.next=null;
}
if(head1==null)target.next=head2;
else target.next=head1;
return mergeHead;
}
//合并两个有序的单链表head1和head2,递归
public static Node mergeSortedListRec(Node head1,Node head2){
if(head1==null)return head2;
if(head2==null)return head1;
if(head1.value>head2.value){
head2.next=mergeSortedListRec(head2.next,head1);
return head2;
}
else{
head1.next=mergeSortedListRec(head1.next,head2);
return head1;
}
}
//对单链表进行排序,归并排序,在排序里面不建议选用递归的合并有序链表算法,如果链表长度较长,很容易出现栈溢出
public static Node listSort(Node head){
Node nex=null;
if(head==null||head.next==null)return head;
else if(head.next.next==null){
nex=head.next;
head.next=null;
}
else{
Node mid=getMiddleNode(head);
nex=mid.next;
mid.next=null;
}
return mergeSortedList(listSort(head),listSort(nex));//合并两个有序链表,不建议递归
}
//对单链表进行排序,插入排序
public Node insertionSortList(Node head) {
if(head==null||head.next==null)return head;
Node pnex=head.next;
Node pnex_nex=null;
head.next=null;
while(pnex!=null){
pnex_nex=pnex.next;
Node temp=head;
Node temp_pre=null;
while(temp!=null){
if(temp.value>pnex.value)break;
temp_pre=temp;
temp=temp.next;
}
if(temp_pre==null){
head=pnex;
pnex.next=temp;
}
else{
temp_pre.next=pnex;
pnex.next=temp;
}
pnex=pnex_nex;
}
return head;
}
//判断一个单链表中是否有环,快慢指针
public static boolean hasCycle(Node head){
boolean flag=false;
Node p1=head;
Node p2=head;
while(p1!=null&&p2!=null){
p1=p1.next;
p2=p2.next.next;
if(p2==p1){
flag=true;
break;
}
}
return flag;
}
//判断两个单链表是否相交,如果相交返回第一个节点,否则返回null
//如果单纯的判断是否相交,只需要看最后一个指针是否相等
public static Node isIntersect(Node head1,Node head2){
Node target=null;
if(head1==null||head2==null)return target;
int len1=getListLength(head1);
int len2=getListLength(head2);
if(len1>=len2){
for(int i=0;i<len1-len2;i++){
head1=head1.next;
}
}else{
for(int i=0;i<len2-len1;i++){
head2=head2.next;
}
}
while(head1!=null&&head2!=null){
if(head1==head2){
target=head1;
break;
}
else{
head1=head1.next;
head2=head2.next;
}
}
return target;
}
//已知一个单链表中存在环,求进入环中的第一个节点,利用hashmap,不要用ArrayList,因为判断ArrayList是否包含某个元素的效率不高
public static Node getFirstNodeInCycleHashMap(Node head){
Node target=null;
HashMap<Node,Boolean> map=new HashMap<Node,Boolean>();
while(head!=null){
if(map.containsKey(head))target=head;
else{
map.put(head, true);
}
head=head.next;
}
return target;
}
//已知一个单链表中存在环,求进入环中的第一个节点,不用hashmap
//用快慢指针,与判断一个单链表中是否有环一样,找到快慢指针第一次相交的节点,此时这个节点距离环开始节点的长度和链表投距离环开始的节点的长度相等
public static Node getFirstNodeInCycle(Node head){
Node fast=head;
Node slow=head;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast)break;
}
if(fast==null||fast.next==null)return null;//判断是否包含环
//相遇节点距离环开始节点的长度和链表投距离环开始的节点的长度相等
slow=head;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}//同步走
return slow;
}
//给出一单链表头指针head和一节点指针delete,O(1)时间复杂度删除节点delete
//可惜采用将delete节点value值与它下个节点的值互换的方法,但是如果delete是最后一个节点,则不行,但是总得复杂度还是O(1)
public static void deleteNode(Node head,Node delete){
//首先处理delete节点为最后一个节点的情况
if(delete==null)return;
if(delete.next==null){
if(head==delete)head=null;
else{
Node temp=head;
while(temp.next!=delete){
temp=temp.next;
}
temp.next=null;
}
}
else{
delete.value=delete.next.value;
delete.next=delete.next.next;
}
return;
}
}
分享到:
相关推荐
一个java实例,用来描述java算法中链表的使用。
Java算法实例-双向链表操作,封装性高,考试、学习都可使用
Java数组链表效率-Java数组和链表三种遍历效率对比 数组和链表.pdf
Java 有序 非循环 双向 链表 算法 实例
* 基于链表实现树结构 */ package dsa; public class TreeLinkedList implements Tree { private Object element;//树根节点 private TreeLinkedList parent, firstChild, nextSibling;//父亲、长子及最大的...
java数组和链表底层-链表的底层原理和实现 数组和链表.pdf
有序链表合并算法动态演示系统是在B/S模式下,在MyEclipse 7.5环境中开发出来的,主要用于教学,对提高教学质量有很大的帮助。
主要介绍了Java实现链表的常见操作算法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
插入,选择排序的链表实现及快速,希尔,冒泡排序算法实现
* 基于位置接口实现的双向链表节点类 */ package dsa; public class DLNode implements Position { private Object element;//数据对象 private DLNode prev;//指向前驱节点 private DLNode next;//指向后继...
很好的,这是一个关于算法的问题,通常的都是用c实现的,但面向对象的java也可以解决这个问提。
* 基于链表实现二叉树 */ package dsa; public class BinTree_LinkedList implements BinTree { protected BinTreePosition root;//根节点 /**************************** 构造函数 ********************...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
java中链表和数组的区别? 数组和链表.pdf
java 数据结构和算法, 排序算法, 数组,链表,二叉树
java数组和链表数据结构的区别 数组和链表.pdf
这个问题的关键在于如何有效地遍历和比较链表中的元素,以实现最优的合并结果。 算法思路 针对这个问题,我们可以采用分治法的思路。首先将多个有序链表两两合并,然后再将这些合并后的链表进行一次合并,直到只剩下...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
练习链表基本操作函数如增删查改;学习链表反转等经典算法的代码实现。 阅读建议:链表算法需要在脑海中模拟指针移动过程,建议边调试代码,边想象链表变化。多做练习,掌握链表操作方法,并应用到更复杂算法题中。
* 单向链表增删改查操作 * */ public class LinkTest { public static void main(String[] args) { Link l=new Link(); l.addNode("A"); l.addNode("B"); l.addNode("C"); l.addNode("D"); l.addNode("E")...