8.删除第一次出在链表出现的key的关节点:
//找删除的前驱 public ListNode searchPery(int key){ ListNode cur = this.head; while(cur.next != null) { if (cur.next.val == key) { return cur; } cur = cur.next; } return null; } //删除第一次出现的关键字为key的节点 public void remove(int key){ if (this.head == null){ System.out.println("单链表为空，不能删除"); return; } if(key == this.head.val){ this.head = this.head.next; return; } ListNode cur = searchPery(key); if(cur == null){ System.out.println("没有你要删除的节点"); return ; } ListNode del = cur.next; cur.next = del.next; }
9.删除所有出在链表出现的key的关节点:
//删除出现所以是key的节点 public ListNode removeAllkey(int key){ if(this.head == null){ return null; } ListNode cur = this.head.next; ListNode pver = this.head; while (cur != null){ if(cur.val == key){ pver.next = cur.next; cur = cur.next; } else { pver = cur; cur = cur.next; } return this.head; } if(this.head.val == key){ this.head = this.head.next; } return this.head; }
10.清空链表:
//清空链表 public void clear(){ //粗暴做法 this.head = null; ListNode curNext = this.head.next; while(this.head != null){ this.head.next = null; this.head = curNext; } } public boolean chkPalindrome(){ if(this.head == null){ return true; } ListNode last = this.head; ListNode slow = this.head; while (last != null && last.next != null){ last = last.next.next; slow = slow.next; } ListNode cur = slow.next; ListNode curNext = cur.next;
2.双向链表的方法实现代码:在已经了解单链表的结构后我们就会发现单链表和双链表的实现是大同小异的
class ListNode { public int val; public ListNode next; public ListNode prev; public ListNode(int val) { this.val = val; } } public class MyLinjedlist { public ListNode head; public ListNode last; //打印链表 public void display() { ListNode cur = this.head; while (cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); } //得到链表的长度 public int size() { int count = 0; ListNode cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } //查找是否包含关键字key是否在链表中 public boolean contains(int key) { if (this.head == null) { return false; } ListNode cur = this.head; while (cur != null) { if (cur.val != key) { cur = cur.next; } else { return true; } } return false; } //头插法 public void addFirst(int data){ ListNode node = new ListNode(data); if(this.head == null){ this.head = node; this.last = node; }else { node.next = this.head; this.head.prev = node; this.head = node; } } //尾插法 public void addLast(int data){ ListNode node = new ListNode(data); if(this.head == null){ this.head = node; this.last = node; }else { this.last.next = node; node.prev = this.last; this.last = node; } } //删除第一次出现关键字为key的节点 public void remove(int key){ ListNode cur = this.head; if(this.head == null){ System.out.println("此链表为空，没有要删除的key值"); return; } while(cur != null){ if(cur.val == key){ if(cur == head){ this.head = this.head.next; if(head != null) { head.prev = null; } else { last = null; } } else { cur.prev.next = cur.next; if (cur.next != null) { //中间位置 cur.next.prev = cur.prev; } else { last = last.prev; } } return; } cur = cur.next; } } //删除所以key的节点 public void removeAll(int key){ ListNode cur = this.head; if(this.head == null){ System.out.println("此链表为空，没有要删除的key值"); return; } while(cur != null){ if(cur.val == key){ if(cur == head){ this.head = this.head.next; if(head != null) { head.prev = null; } else { last = null; } } else { cur.prev.next = cur.next; if (cur.next != null) { //中间位置 cur.next.prev = cur.prev; } else { last = last.prev; } } } cur = cur.next; } } //任意位置插入，第一个数据节点默认为0下标 public void addIndex(int index,int data){ ListNode node = new ListNode(data); if(index == 0){ addFirst(data); return; } if (index == size()-1){ addLast(data); return; } ListNode cur = this.head; while (index != 0){ index--; cur = cur.next; } node.next = cur; node.prev= cur.prev; cur.prev.next = node; cur.prev = node; } //清理链表 public void clear(){ while (head != null){ ListNode curNext = this.head.next; head.next = null; head.prev = null; head = curNext; } last = null; } }
总结
根据读完本文后大家会对链表有更深的理解,并且能够掌握对方法的深层理解,相信大家在过后时间能够保持求学的态度,我们一起加油!offer拿到手软!对博主感兴趣可以关注博主,我会继续更新博客,努力完善我的文章内容不会辜负大家的期待!
