自己写个单链表
package com.cn.jichu.day07; public class LinkedList<E> { private class Node{ public Node next; public E data; public Node(Node next,E data) { this.next = next; this.data = data; } public Node(E data) { this(null,data); } public Node() { this(null,null); } } /** * 虚拟头节点 */ private Node dummyHead; /** * 当前链表大小 */ private int size; public LinkedList() { dummyHead = new Node(); size = 0; } /** * 获取链表中有多少个元素 * @return */ public int getSize(){ return size; } /** * 判断链表是否为空 * @return */ public boolean isEmpty(){ return size == 0; } /** * 在链表的某个位置添加元素 * @param index * @param e */ public void add(int index, E e){ if(index < 0 || index > size){ throw new IllegalArgumentException("大哥，请收回你的非法的index！"); } //找到当前index的前一个节点 Node prev = dummyHead; for(int i = 0;i<index;i++){ prev = prev.next; } Node node = new Node(e); node.next = prev.next; prev.next = node; size ++ ; } /** * 向首节点添加元素 * @param e */ public void addFirst(E e){ add(0,e); } /** * 向尾节点添加元素 * @param e */ public void addLast(E e){ add(size,e); } /** * 获取第index元素 * @param index * @return */ public E get(int index){ if(index < 0|| index> size){ throw new IllegalArgumentException("大哥，请收回你的非法的index！"); } Node cur = dummyHead.next; for(int i=0;i<index;i++){ cur = cur.next; } return cur.data; } /** * 获取首节点元素 * @return */ public E getFirst(){ return get(0); } /** * 获取尾节点元素 * @return */ public E getLast(){ return get(size-1); } /** * 删除第index个节点 * @param index * @return */ public E deleteByIndex(int index){ if(index < 0|| index> size){ throw new IllegalArgumentException("大哥，请收回你的非法的index！"); } //定义一个index前的节点,找到index前一个节点 Node prev = dummyHead; for(int i=0;i<index;i++){ prev = prev.next; } //定义一个返回去的节点,为前一个节点的下一个节点，就是要删除的当前节点 Node retNode = prev.next; //将前一个节点的next 指向 当前节点的next 将要删除的节点踢出去 prev.next = retNode.next; //要删除的节点还连着 next呢，要将其为null，彻底踢出去，不占用内存 ，要不然一直消耗内存不释放 retNode.next = null; size --; return retNode.data; } /** * 删除首节点 * @return */ public E deleteByFirst(){ return deleteByIndex(0); } public E deleteByLast(){ return deleteByIndex(size-1); } /** * 根据数值删除链表的节点 * @param data * @return */ public void deleteByData(E data){ Node prev = dummyHead; while (prev.next!=null){ if(prev.next.data.equals(data)){ break; } prev = prev.next; } if(prev.next != null){ Node delNode = prev.next; prev.next = delNode.next; delNode.next = null; } } /** * 修改第index位置的节点 * @param index * @param e */ public void update(int index,E e){ if(index < 0|| index> size){ throw new IllegalArgumentException("大哥，请收回你的非法的index！"); } Node prev = dummyHead; for(int i=0;i<index;i++){ prev = prev.next; } prev.next.data = e; } /** * 判断链表中是否有该元素 * @param e */ public boolean isData(E e){ boolean ret = false; Node node = dummyHead; while (node.next!=null){ if(node.next.data.equals(e)){ return true; } node = node.next; } return ret; } /** * 链表倒置 * @param linkedList */ public void reverse(LinkedList linkedList){ if(linkedList.getSize() == 0){ throw new IllegalArgumentException("当前链表为空，请勿倒置"); } Node cur = linkedList.dummyHead.next; Node prev = null; while (cur!=null){ Node next = cur.next; cur.next = prev; prev = cur; cur = next; } dummyHead.next = prev; } /** * 查找链表中间节点 * @return */ public E getMod(LinkedList linkedList){ if(linkedList.getSize() == 0){ throw new IllegalArgumentException("当前链表为空"); } Node slow = linkedList.dummyHead.next; Node fast = linkedList.dummyHead.next.next; while (fast!=null && fast.next!=null){ if(!slow.data.equals(fast.data)){ slow = slow.next; fast = fast.next.next; } } return slow.data; } /** * 生成一个环形单链表 * @return */ public LinkedList getCircularLinked(LinkedList linkedList,int index){ if(index < 0|| index> size){ throw new IllegalArgumentException("大哥，请收回你的非法的index！"); } Node indexNode = dummyHead.next; Node cur = linkedList.dummyHead;; for(int i =0;i<index;i++){ indexNode = indexNode.next; } while (cur.next!=null){ cur = cur.next; } cur.next = indexNode.next; return linkedList; } /** * 判断是否是环形链表 * @return */ public boolean isCircularLinked(LinkedList linkedList){ boolean ret = false; Node slow = linkedList.dummyHead.next; Node fast = linkedList.dummyHead.next.next; while (fast!=null && fast.next!=null){ if(slow.equals(fast)){ ret = true; break; }else { slow = slow.next; fast = fast.next; } } return ret; } /** * 删除倒数第N个节点 * @return */ public LinkedList deleteNthFromEnd(LinkedList linkedList,int index){ Node first = linkedList.dummyHead.next; if(index < 0|| index> size){ throw new IllegalArgumentException("大哥，请收回你的非法的index！"); } //1 当index为是当前链表的大小，删除的就是头结点 if(index == size){ dummyHead.next = first.next; return linkedList; } //one节点向后移动index位 Node one = linkedList.dummyHead.next; for(int i=0;i<index;i++){ one = one.next; } //two节点向后移动一位，one节点向后移动index后与two节点同时向后移动一位，直到one节点到达尾部（one节点比two节点快） Node two = linkedList.dummyHead.next; while (one.next!=null){ one = one.next; two = two.next; } two.next = two.next.next; return linkedList; } /** * 验证单链表是否是回文链表 * @return */ public boolean isHuiWen(LinkedList linkedList){ boolean ret = false; //1 先将原链表存储一份新的 LinkedList<E> newLinkedList = new LinkedList<>(); Node node = linkedList.dummyHead.next; while (node!=null){ newLinkedList.addLast(node.data); node = node.next; } //2 找到链表的中间节点,慢节点就是从中间节点向后的链表 Node slow = linkedList.dummyHead.next; Node fast = linkedList.dummyHead.next.next; while (fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; } //3 从中间节点向后的链表进行倒置 Node cur = slow; Node prev = null; while (cur!= null){ Node next = cur.next; cur.next = prev; prev = cur; cur = next; } //3 倒置的链表与新的链表进行对比 Node p = prev; Node q = newLinkedList.dummyHead.next; // P节点少 while (p.next!=null){ if(p.data.equals(q.data)){ ret = true; }else{ ret = false; break; } p = p.next; q = q.next; } return ret; } @Override public String toString(){ StringBuilder res = new StringBuilder(); Node cur = dummyHead.next; while(cur != null){ res.append(cur.data + "->"); cur = cur.next; } res.append("NULL"); return res.toString(); } }