java实现链表相关操作

悠悠 2021-11-10 14:08 298阅读 0赞

### 文章目录 ###

*   *  链表
     *   *  1.实现单链表的基本操作
         *  2.从链表中删除重复数据
         *  3.找出单链表的倒数第k个元素
         *  4.实现链表反转
         *  5.从尾到头输出单链表
         *  6.寻找单链表的中间节点
         *  7.判断一个链表是否带环
         *  8.在不知道头指针的情况下删除指定节点
         *  9.如何判断两个链表相交

## 链表 ##

### 1.实现单链表的基本操作 ###

package com.DS;
    
    class Node{ 
        Node next = null;
        int data ;
        public Node( int data){ 
            this.data = data;
        }
    }
    
    public class LinkedList { 
        Node head = null;
        //在链表最后插入数据
        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;
            return;
        }
        //删除第index个节点
        public void delete(int index){ 
            if(head == null){ 
                System.out.println("链表为空，无法进行删除操作");
                return;
            }
            if(index<1||index>length()){ 
                System.out.println("删除索引有误，无法进行删除操作");
                return;
            }
            //要删除的节点为头结点
            if (index == 1){ 
                head = head.next;
            }
            int i = 2;
            Node preNode = head;
            Node curNode = preNode.next;
            while (curNode != null){ 
                if (i == index){ 
                    preNode.next = curNode.next;
                    return;
                }
                preNode = curNode;
                curNode = curNode.next;
            }
        }
        //返回链表长度
        public int length(){ 
            int len = 0;
            Node temp = head;
            while (temp != null){ 
                len++;
                temp = temp.next;
            }
            return len;
        }
        //对链表进行排序，返回排序后的头结点
        public Node orderList(){ 
           Node nextNode = null;
           Node curNode = head;
           int temp;
           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 node = head;
            while (node!=null){ 
                System.out.print(node.data+"——>");
                node = node.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) { 
            LinkedList list = new LinkedList();
            list.addNode(3);
            list.addNode(4);
            list.addNode(7);
            list.addNode(6);
            list.addNode(5);
            list.addNode(2);
            System.out.println("链表长度为"+list.length());
            System.out.println("原链表为：");
            list.printList();
            list.delete(2);
            System.out.println("删除操作后链表为");
            list.printList();
            System.out.println("排序后链表为");
            list.orderList();
            list.printList();
        }
    }

### 2.从链表中删除重复数据 ###

//方法1
       public void deleteduplecate(){ 
            Hashtable<Integer,Integer> table = new Hashtable<>();
            Node temp = head;
            Node pre = null;
            while(temp!=null){ 
                if(table.contains(temp.data)){ 
                    pre.next = temp.next;
                }
                else { 
                    table.put(temp.data,1);
                    pre = temp;
                }
                temp = temp.next;
    
            }
        }
        //方法2
        public void deleteduplecate(){ 
           Node p = head;
           while (p!=null){ 
               Node q = p;
               while (q.next!=null){ 
                   if (q.next.data == p.data){ 
                       q.next = q.next.next;
                   }
                   else
                       q = q.next;
               }
               p = p.next;
           }
        }

### 3.找出单链表的倒数第k个元素 ###

思路：查找过程中设置两个指针，让其中一个指针先走k-1步，当他的指针值为null时，另一个指针所指的位置就是倒数第k个元素。（java中没有指针，故采用引用）

public Node findkElem(int k) { 
            if (k < 1||k>length()) { 
                return null;
            }
            Node p1 = head;
            Node p2 = head;
            for (int i = 0; i < k ; i++) { 
                p1 = p1.next;
            }
            while (p1!=null){ 
                p1 = p1.next;
                p2 = p2.next;
            }
            return p2;
        }

### 4.实现链表反转 ###

public void ReverseList(){ 
            if (head == null||head.next==null){ 
                this.head= head;
            }
            Node preNode = null;
            Node curNode = head;
            Node nextNode ;
            while (curNode!=null){ 
                nextNode = curNode.next;
                curNode.next = preNode;
                preNode = curNode;
                curNode = nextNode;
            }
            this.head = preNode;
        }

### 5.从尾到头输出单链表 ###

public void printListReversely(Node head){ 
            if (head!=null){ 
                printListReversely(head.next);
                System.out.println(head.data);
            }
        }

### 6.寻找单链表的中间节点 ###

思路：有两个指针同时从头开始遍历，一个快指针一次走两步，一个慢指针一次走一步，当快指针走到链表尾部时，慢指针刚好到达链表中部（当链表长度为奇数时，慢指针刚好到达链表中间位置；当链表长度为偶数时，慢指针指向的节点以及下一个节点都是链表的中间节点）

public Node searchMid(Node head){ 
            Node fast = this.head;
            Node slow = this.head;
            while(fast!=null && fast.next!=null && fast.next.next!=null){ 
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

### 7.判断一个链表是否带环 ###

思路：定义两个指针fast和slow，其中fast每次前进两步，slow每次前进一步，每移动一次两个都要进行比较，直到当快指针等于慢指针时，就证明这个链表是带环的单向链表；当fast先走到尾部为null值时就证明为无环链表。

public boolean isLoop(Node head){ 
            Node fast = head;
            Node slow = head;
            while (fast!=null&&fast.next!=null){ 
                fast = fast.next.next;
                slow = slow.next;
                if (fast==slow){ 
                    return true;
                }
            }
            return  !(fast==null||fast.next==null);
        }

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

分为两种情况来讨论：  
1.若待删除的节点为链表尾节点，则无法删除，因为删除后无法使其前驱结点的next指向null；  
2.若待删除的节点不是尾节点，则可以通过交换这个节点与后继节点的值，然后删除后继节点。

public boolean deleteNode(Node n){ 
            if (n==null||n.next==null){ 
                return false;
            }
            int temp = n.data;
            n.data=n.next.data;
            n.next.data=temp;
            n.next = n.next.next;
            return true;    
        }

### 9.如何判断两个链表相交 ###

思路：如果两个链表相交，那么它们一定有着相同的尾节点，分别遍历两个链表，记录它们的尾节点，如果它们的尾节点相同，那么这两个链表相交，否则不相交。

public boolean isIntersect(Node h1,Node h2){ 
            if (h1==null||h2==null){ 
                return false;
            }
            Node tail1=h1;
            Node tail2=h2;
            while (tail1.next!=null){ 
                tail1 = tail1.next;
            }
            while (tail2.next!=null){ 
                tail2 = tail2.next;
            }
            return tail1==tail2;
        }

引申：如果两个链表相交，如何找到它们相交的第一个节点？  
首先分别计算两个链表的长度len1和len2（假设len1>len2）,接着先对链表1遍历（len1-len2）个节点到节点p，此时节点p与链表2的head到相交点距离相同，此时同时遍历两条链表，直到遇到相同的节点为止，此节点就是他们相交的第一个节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BlcmZlY3RtYXRjaF9H_size_16_color_FFFFFF_t_70]

public static Node getFirstMeetNode(Node head1,Node head2){ 
            if (head1==null||head2==null){ 
                return null;
            }
            Node tail1 = head1;
            Node tail2 = head2;
            int len1 = 1;
            int len2 = 1;
            while (tail1.next!=null){ 
                tail1 = tail1.next;
                len1++;
            }
            while (tail2.next!=null){ 
                tail2 = tail2.next;
                len2++;
            }
            //两链表不相交
            if (tail1!=tail2){ 
                return null;
            }
            Node h1=head1;
            Node h2=head2;
            if (len1>len2){ 
                int d=len1-len2;
                while (d!=0){ 
                   h1 = h1.next;
                   d--;
                }
            }else{ 
                int d = len2-len1;
                while (d!=0){ 
                    h2=h2.next;
                    d--;
                }
            }
            while (h1!=h2){ 
                h1=h1.next;
                h2=h2.next;
            }
            return h1;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BlcmZlY3RtYXRjaF9H_size_16_color_FFFFFF_t_70]: /images/20211109/8038bf85fb9e4c8dbf60c89c5e206eed.png