`
隐形的翅膀
  • 浏览: 498258 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

JAVA中关于链表的操作和基本算法

 
阅读更多
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实现。 1. **创建双向链表** 创建双向链表首先要定义链表节点类,包含数据域和两个指针域,分别指向前后节点。Java代码如下: ```java class Node { int data; ...

    java算法全卷(包括基本算法和图算法)

    在《Addison Wesley - Algorithms in Java》第三版的Part 1-4中,你将找到关于基本算法的详细解释和示例。Part 5则专门探讨了图算法,提供了深入的理论和实践指导。这两部分结合,为Java开发者提供了一个全面的算法...

    java 数据结构 链表

    总结来说,Java中的链表是一种灵活的数据结构,适用于动态数据集的管理,提供了插入、删除和遍历等基本操作。理解链表的工作原理以及如何在Java中实现和使用链表,是每个Java开发者必备的基础技能。通过深入学习和...

    java 单链表和双向链表的实现

    本话题主要探讨两种常用的数据结构——单链表和双向链表在Java中的实现,以及相关的操作,如在头部添加节点、在尾部添加节点、遍历、逆置和删除。 首先,我们来理解单链表和双向链表的基本概念。单链表是一种线性...

    Java数组链表效率-Java数组和链表三种遍历效率对比 数组和链表.pdf

    Java 中的数组和链表是两种常用的数据结构,它们都可以用来存储和操作数据。然而,在实际开发中,选择合适的数据结构和遍历方式对程序的性能和效率有着非常重要的影响。下面我们将对 Java 中数组和链表的三种遍历...

    Java有序非循环双向链表算法实例

    在Java编程中,有序非循环双向链表是一种重要的数据结构,它在许多复杂的数据操作和算法实现中扮演着核心角色。有序意味着链表中的元素按照特定的顺序排列,非循环则表示链表的首节点和尾节点之间没有链接,使得遍历...

    有序链表合并算法动态演示系统的毕业设计文档及系统 JAVA

    有序链表合并算法是计算机科学中的一个重要概念,特别是在数据结构和算法分析中。这个算法的主要目的是将两个或多个已排序的链表合并成一个单一的、有序的链表。在本毕业设计中,该算法被动态地演示,使得学生能够更...

    链表演示程序(数据结构课程设计)

    这个项目的目标是帮助学生理解和实践链表的基本操作,如初始化、插入、删除和搜索。 首先,让我们深入了解链表的概念。链表不同于数组,它不是一个连续的内存空间。在链表中,每个元素称为节点,包含两个部分:数据...

    java 实现倒序链表

    链表作为一种常见的数据结构,在计算机科学中有着广泛的应用,而倒序链表则是链表操作中的一项基本技能,对于理解链表的工作原理和提升编程能力都有着重要的作用。 #### 倒序链表的概念 倒序链表指的是将原链表中...

    操作系统调度算法java源代码

    在Java中实现这些调度算法,通常会涉及到数据结构如链表或队列,用于存储和管理进程状态,以及一些辅助方法来模拟进程的创建、执行和等待。此外,为了模拟操作系统的环境,可能还需要实现一个模拟的CPU和时间片系统...

    java链表 个人总结

    总的来说,理解和掌握Java链表对于任何Java开发者来说都是必要的,无论是为了优化算法效率,还是为了更好地进行多语言编程。通过阅读“笔记”13链表.pdf和实际编写代码,可以进一步加深对链表的理解和应用。在实践中...

    java基于链表实现树结构(算法源码)

    * 基于链表实现树结构 */ package dsa; public class TreeLinkedList implements Tree { private Object element;//树根节点 private TreeLinkedList parent, firstChild, nextSibling;//父亲、长子及最大的...

    双端链表和双向链表Java代码

    接下来,我们创建一个双端链表类(DoubleLinkList.java),它包含对链表的基本操作,如添加、删除、遍历等。这些方法会使用节点类中的prev和next属性来维护链表的结构。 双向链表与双端链表的主要区别在于,双向...

    2022年Java语言中链表和双向链表Java教程.docx

    《2022年Java语言中链表和双向链表Java教程》 链表作为一种基础且重要的数据结构,广泛应用于编程领域,特别是在Java语言中。虽然Java不直接提供指针,但通过对象引用,我们可以轻松地实现链表的构建。在Java中,...

    堆栈链表与队列链表的基本操作

    本篇文章将详细探讨堆栈链表和队列链表的基本操作。 首先,让我们了解堆栈(Stack)的概念。堆栈是一种后进先出(LIFO,Last In First Out)的数据结构,类似于日常生活中的叠盘子。在堆栈中,最后加入的元素将是第...

    Java版链表模板类

    综上所述,`CList.java`和`CList2.java`文件中封装了Java的循环链表模板类,提供了插入、删除、查找等基本操作,并考虑了泛型设计以适应不同类型的数据。`CList2`可能是对`CList`的增强,例如实现了双向链表。这个...

    JAVA双向链表反转实现

    接下来,我们需要创建一个双向链表类,用于维护链表的头部和尾部,并提供添加、删除等基本操作: ```java public class DoublyLinkedList { private Node head; private Node tail; // 添加节点到链表尾部 ...

    MLDN魔乐JAVA_13链表.MLDN魔乐JAVA_13链表.rar

    链表是一种基础且重要的数据结构,它在计算机科学和编程,尤其是Java中有着广泛的应用。...这个教程可能包括了链表的定义、基本操作的示例代码、性能分析以及常见面试题的解答,对于提升你的Java编程技能大有裨益。

Global site tag (gtag.js) - Google Analytics