java实现单链表的相关内容

class Node{ public int data; public Node next; public Node(){ } public Node(int data){ this.data = data; } } class LindedList { public Node head; //头插 public void addFirst(int data) { Node node = new Node(data); if (this.head == null) { this.head = node; } else { node.next = this.head; this.head = node; } } //尾插 public void addLast(int data) { Node node = new Node(data); if (this.head == null) { this.head = node; } else { Node cur = this.head; while (cur.next != null) { cur = cur.next; } cur.next = node; } } //检查插入的位置是否存在 private void checkIndex(int index) { if (index < 0 || index > getLength()) { throw new IndexOutOfBoundsException("不合法"); } } //获取线性表的长度 private int getLength() { int count = 0; Node cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } private Node searchIndex(int index) { int count = 0; Node cur = this.head; while (count < index - 1) { count++; cur = cur.next; } return cur; } //任意位置插入 public boolean addIndex(int index, int data) { checkIndex(index); if (index == 0) { //首插 addFirst(data); return true; }//有节点 Node cur = searchIndex(index);//前驱 //插入 Node node = new Node(data); node.next = cur.next; cur.next = node; return true; } private Node searchPrev(int key) { Node prev = this.head; while (prev.next != null) { if (prev.next.data == key) { return prev; } prev = prev.next; } return null; } //删除第一个关键字key public void remove(int key) { if (this.head.data == key) { this.head = this.head.next; return; } Node prev = searchPrev(key); if (prev == null) { return; } Node del = prev.next; prev.next = del.next; } /*1、 删除所有的关键字 删除链表中等于给定值 */ public void removeAllKey(int key) { Node prev = this.head;//前驱 Node cur = this.head.next; //cur当前要删除的节点 while (cur != null) { if (prev.next.data == key) { prev.next = cur.next; cur = cur.next; } else { prev = cur; cur = cur.next; } } if (this.head.data == key) { this.head = this.head.next; } } //清空 public void clear() { this.head = null; } /*2、 逆置链表 反转一个单链表 */ public Node reverseList() { Node prev = null; Node cur = this.head;//当前要翻转的节点 Node newHead = null; while (cur != null) { Node curNext = cur.next; if (curNext == null) {// newHead = cur; } cur.next = prev; prev = cur; cur = curNext; } return newHead; } //打印链表 public void display() { Node cur = this.head; while (cur != null) { System.out.print(cur.data + " "); cur = cur.next; } System.out.println(); } public void display2(Node newHead) { Node cur = newHead; while (cur != null) { System.out.print(cur.data + " "); cur = cur.next; } System.out.println(); } /*3、 返回一个链表的中间节点 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点 */ public Node middleNode() { Node fast = this.head; Node slow = this.head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } /* 4、 返回倒数第K个节点 输入一个链表，输出该链表中倒数第k个结点 */ public Node findKthToTail(int k) { Node fast = this.head; Node slow = this.head; while (k - 1 > 0) { if (fast.next != null) { fast = fast.next; k--; } else { System.out.println("没有这个节点"); return null; } } while (fast.next != null) { fast = fast.next; slow = slow.next; } return slow; } /* 5、 // 以给定值x为基准将链表分割成两部分， // 所有小于x的结点排在大于或等于x的结点之前 */ public Node partition(int x) { Node beforeStart = null; Node beforeEnd = null; Node afterStart = null; Node afterEnd = null; Node cur = this.head; while (cur != null) { Node curNext = cur.next; cur.next = null; if (cur.data < x) { //第一次插入到beforeStart if (beforeStart == null) { beforeStart = cur; beforeEnd = cur; } else { beforeEnd.next = cur; beforeEnd = cur; } } else {//cur.data >= x if (afterStart == null) { afterStart = cur; afterEnd = cur; } else { afterEnd.next = cur; afterEnd = cur; } } cur = curNext; } //如果第一个线段没有数据 没有比基准小的数据 if (beforeStart == null) { return afterStart; } beforeEnd.next = afterStart; return beforeStart; } /*7、 在一个排序的链表中，存在重复的结点， 请删除该链表中重复的结点，重复的结点不保留，返回链表头指针 */ public Node deleteDuplicatio() { Node newHead = new Node(-1); Node tmp = newHead; Node cur = this.head; while (cur != null) { if (cur.next != null && cur.data == cur.next.data) { while (cur.next != null && cur.data == cur.next.data) { cur = cur.next; } cur = cur.next; tmp.next = cur; } else { tmp.next = cur; tmp = tmp.next; cur = cur.next; } } return newHead.next; } /*8、 链表的回文结构 如是回文，则输出为true */ public boolean chkPalindrom(){ Node fast = this.head; Node slow = this.head; if(this.head == null){ return false; } if(this.head.next == null){ return true; } while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } Node p = slow.next; while (p!=null){//翻转 Node pNext = p.next;; p.next = slow; slow = p; p = pNext; if(p != null){ pNext = p.next; } } //判断 while (this.head != slow) { if (this.head.data != slow.data) { return false; } if (this.head.next == slow) {//偶数 遍历到中间的时候 即遍历完 return true; } this.head = this.head.next; slow = slow.next; } return true; } //创建一个环链表 public void creatCycle(){ Node cur = this.head; while (cur.next != null){ cur = cur.next; } cur.next = this.head.next.next; } /*10、 给定一个链表，判断链表中是否有环。 */ public boolean hasCycle() { Node fast = this.head; Node slow = this.head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { return true; } } return false; } //11、 // 给定一个链表，返回链表开始入环的第一个节点。 // 如果链表无环，则返回 null public Node detectCycle() { Node fast = this.head; Node slow = this.head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } if (fast == null || fast.next == null) { return null; } fast = this.head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } }