7.线性表：实现单链表的各种操作

傷城~ 2023-10-13 10:53 125阅读 0赞

**目 录**

定义节点类：

一、单链表的基本操作

二、删除重复数据

三、找到倒数第k个元素

四、实现链表的反转

五、从尾到头输出链表

六、找到中间节点

七、检测链表是否有环

方法一、快慢指针移动判断

方法二：使用Set<>集合记录Node元素，如果有重复元素则认为有环

扩展：如果链表有环，找到有环的入口点是哪个节点

八、在不知道头指针的情况下删除指定节点

九、如何判断两个链表是否相交并找出相交节点

--------------------

## 定义节点类： ##

class Node{
        public int data;
        public Node next;
        
        public NodeList(int num){
            this.data = num;
        }
    }

## 一、单链表的基本操作 ##

实现单链表的基本操作包括增加节点、删除节点、排序、打印、计算长度。

/**
     * @author Administrator
     * 实现单链表的基本操作,增加节点、删除节点、排序、打印、计算长度
     */
    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;
            }
            //add Node to end
            tmp.next=newNode;
        }
        
        /**
         * @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 返回链表的长度length
         */
        public int length(){
            int length=0;
            Node tmp=head;
            while(tmp!=null){
                length++;
                tmp=tmp.next;
            }
            return length;
        }
        /**
         * 对链表进行排序
         * @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.print(tmp.data+" ");
                tmp=tmp.next;
            }
            System.out.println();
        }
    }

## 二、删除重复数据 ##

/**
         * 从链表中删除数据的第一种方法
         * 遍历链表，把遍历到的数据存到一个Hashtable中，在遍历过程中若当前访问的值在Hashtable
         * 中存在，则可以删除
         * 优点：时间复杂度低    缺点：需要额外的存储空间来保存已访问过得数据
         */
        public void deleteDuplecate1(){
            Hashtable<Integer,Integer> table=new Hashtable<Integer,Integer>();
            Node tmp=head;
            Node pre=null;
            while (tmp!=null) {
                if(table.containsKey(tmp.data))
                    pre.next=tmp.next;
                else{
                    table.put(tmp.data, 1);
                    pre=tmp;
                }
                tmp=tmp.next;
            }
        }
        /**
         * 从链表中删除重复数据的第二种方法
         * 双重循环遍历
         * 优缺点很明显
         */
        public void deleteDuplecate2(){
            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个元素 ##

/**
         * @param k：找到链表中倒数第k个节点
         * @return 该节点
         * 设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第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++) 
                p2=p2.next;
            while (p2.next!=null) {
                p2=p2.next;
                p1=p1.next;
            }
            return p1;
        }

## 四、实现链表的反转 ##

/**
         * 实现链表的反转
         * @param head链表的头节点
         */
        public void reverseIteratively(Node head){
            Node pReversedHead=head;
            Node pNode=head;
            Node pPrev=null;
            while (pNode!=null) {
                Node pNext=pNode.next;
                if(pNext==null)
                    pReversedHead=pNode;
                pNode.next=pPrev;
                pPrev=pNode;
                pNode=pNext;        
            }
            this.head=pReversedHead;
        }

## 五、从尾到头输出链表 ##

/**
         * 通过递归从尾到头输出单链表
         * @param head
         */
        public void printListReversely(Node head){
            if(head!=null){
                printListReversely(head.next);
                System.out.print(head.data+" ");
            }
        }

## 六、找到中间节点 ##

/**
         * 查询单链表的中间节点
         * 定义两个指针，一个每次走一步，一个每次走两步...
         * @param head
         * @return q为中间节点
         */
        public Node searchMid(Node head){
            Node q=head;
            Node p=head;
            while (p!=null&&p.next!=null&&p.next.next!=null) {
                q=q.next;
                p=p.next.next;
            }
            return q;
        }

## 七、检测链表是否有环 ##

建立一个有环链表：

//初始化一个有环的链表Node
    Node nodeA = new Node("A");
    Node nodeB = new Node("B");
    Node nodeC = new Node("C");
    Node nodeD = new Node("D");
    Node nodeE = new Node("E");
    Node nodeF = new Node("F");
    
    nodeA.next = nodeB;
    nodeB.next = nodeC;
    nodeC.next = nodeD;
    nodeD.next = nodeE;
    nodeE.next = nodeF;
    nodeF.next = nodeD;//此时F节点又指向了D节点，已经产生了环状

### 方法一、快慢指针移动判断 ###

首先如何判断链表是否有环，这个时候首先需要知道链表是否为空，如果不为空，则继续判断。

思路：首先定义两个变量，一个fast,一个slow，让fast 每次走两步，slow每次走一步，当fast和slow相遇时，即是该链表存在环结构。如果该链表为无环结构，则当遍历完这个链表时也不会相遇。即是返回false。

图例如下：

图中为了说明情况，

fast指针初始标记为f0,每移动一次加1，如f1,f2,f3....

slow指针初始标记为s0,每移动一次加1，如s1,s2,s3....

![f0343fc1b7384e0c83bddc80586cc0f4.png][]

/**
         * 判断链表是否有环 （快慢指针的方式）
         *                                       <-----------------
         *                                      |                 |
         *          [A]  ->  [B]  ->  [C]  ->  [D]  ->  [E]  ->  [F]
         *
         * 初始指针  f0
         *          s0
         * 第一次            s1       f1
         * 第二次                     s2                f2
         * 第三次                             s3/f3
         * 本例中即第三次遍历就判断出链表有环
         * @param node
         * @return
         */
        private boolean hasCycle(Node node) {
            if (node == null) {
                return false;
            }
            Node fast = node;
            Node slow = node;
            //此字段仅用来记录遍历次数
            int traverseCount = 0;
            while (fast != null && fast.next != null && slow != null) {
                fast = fast.next.next;//移动2步
                slow = slow.next;//移动1步
                traverseCount ++;
                if (fast == slow) {
                    //如果碰面，就代表有环
                    Log.d(TAG, "hasCycle==>有环...traverseCount="+traverseCount);
                    return true;
                }
                Log.d(TAG, "hasCycle==>已经遍历次数...traverseCount="+traverseCount);
            }
            Log.d(TAG, "hasCycle==>无环");
            return false;
        }

### 方法二：使用Set<>集合记录Node元素，如果有重复元素则认为有环 ###

/**
         * 通过Set集合记录值的方式，如果有重复的数据，就代表有环
         * @param node
         * @return
         */
        private boolean hasCycle2(Node node) {
            Set<Node> nodeSet = new HashSet<>();
            //此字段仅用来记录遍历次数
            int traverseCount = 0;
            while (node != null) {
                if (nodeSet.contains(node)) {
                    Log.d(TAG, "hasCycle2==>有环...traverseCount="+traverseCount);
                    return true;
                }
                traverseCount ++;
                Log.d(TAG, "hasCycle2==>traverseCount="+traverseCount);
                nodeSet.add(node);
                node = node.next;
            }
            Log.d(TAG, "hasCycle2==>无环");
            return false;
        }

### 扩展：如果链表有环，找到有环的入口点是哪个节点 ###

如上图，入口点就是节点D，下面要找到这个节点

思路：s=vt（路程=速度\*时间）用方程思想列等式解。因为路程知道，速度知道（二倍关系），时间也知道（相等），所以可以列等式求关系。再用代码体现出关系，就可以解决这道题了。

如图：假设链表是Link fast是快的那个指针，Slow是慢的呢个指针，蓝色是fast走过的路程，绿色是slow走过的路程K是环的入口，P是快慢指针相遇的地方，a，b，c 分别代表三段长度。

![54f363b4988044a5af975a90a16f867b.png][]

所以图就可以变成：

![123d06f10c0049f2b15f3ac2c1233622.png][]

然后，让指针从 相遇点p 和 起始点first 同时遍历，这样由于 c = a , 所以p和first在k相遇，而k就是入口点。

/**
         * 如果有环，获取相遇点的node
         * @param node
         * @return
         */
        private Node getMeetNode(Node node) {
            if (node == null) {
                return null;
            }
            Node fast = node;
            Node slow = node;
            //此字段仅用来记录遍历次数
            int traverseCount = 0;
            while (fast != null && fast.next != null && slow != null) {
                fast = fast.next.next;//移动2步
                slow = slow.next;//移动1步
                traverseCount ++;
                if (fast == slow) {
                    //如果碰面，就代表有环
                    Log.d(TAG, "hasCycle==>有环...traverseCount="+traverseCount);
                    return fast;
                }
                Log.d(TAG, "hasCycle==>已经遍历次数...traverseCount="+traverseCount);
            }
            return null;
        }
    
        /**
         * 如果有环，获取环出现的入口点
         * @return
         */
        public Node getCycleEntry(Node node) {
            Node meetNode = getMeetNode(node);
            Node p = meetNode;//相遇点元素的指针
            Node first = node;//链表第一个元素的指针
            while(p != first) {
                //两个指针都进行移动，当相等的时候就找到了入口点
                first = first.next;
                p = p.next;
            }
            return p;
        }
    
       /**
        * 将入口点打印出来：
        */
        Node entryNode = getCycleEntry(nodeA);
        Log.d(TAG, "有环的链表入口点Node Value="+entryNode.value);

## 八、在不知道头指针的情况下删除指定节点 ##

/**
         * 在不知道头指针的情况下删除指定节点
         * 链表尾节点无法删除，因为删除后无法使其前驱节点的next指针置为空
         * 其他节点，可以通过交换这个节点与其后继节点的值，然后删除后继节点
         * @param n
         * @return
         */
        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;
        }

## 九、如何判断两个链表是否相交并找出相交节点 ##

/**
         * 判断两个链表是否相交
         * 如果两个链表相交，则肯定有相同的尾节点，遍历两个链表，记录尾节点，看是否相同
         * @param h1链表1的头节点
         * @param h2链表2的头结点
         * @return 是否相交
         */
        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;
        }
        /**
         * 找出相交的第一个节点
         * @param h1
         * @param h2
         * @return
         */
        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--;
                }    
            }
            if(len1<len2){
                int d=len2-len1;
                while(d!=0){
                    t2=t2.next;
                    d--;
                }    
            }
            while(t1!=t2){
                t1=t1.next;
                t2=t2.next;
            }
            return t1;
        }

[6.线性表：顺序表和链表的优缺点\_IT小悟的博客-CSDN博客本章节主要介绍顺序表和链表的定义、特点、优点、缺点和适应环境![favicon32.ico][]https://blog.csdn.net/speedwalkman/article/details/131512304][6._IT_-CSDN_favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_131512304]

[f0343fc1b7384e0c83bddc80586cc0f4.png]: https://img-blog.csdnimg.cn/f0343fc1b7384e0c83bddc80586cc0f4.png
[54f363b4988044a5af975a90a16f867b.png]: https://img-blog.csdnimg.cn/54f363b4988044a5af975a90a16f867b.png
[123d06f10c0049f2b15f3ac2c1233622.png]: https://img-blog.csdnimg.cn/123d06f10c0049f2b15f3ac2c1233622.png
[favicon32.ico]: https://g.csdnimg.cn/static/logo/favicon32.ico
[6._IT_-CSDN_favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_131512304]: https://blog.csdn.net/speedwalkman/article/details/131512304