头插法、尾插法、链表长度test-c-master.zip

import java.util.List; public class MySingleList { static class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head;//当前链表的头节点的引用 public void createLink() { ListNode node1 = new ListNode(12); ListNode node2 = new ListNode(45); ListNode node3 = new ListNode(23); ListNode node4 = new ListNode(90); node1.next = node2; node2.next = node3; node3.next = node4; head = node1;//局部变量node1234最后被回收 } //遍历链表 public void display() { ListNode cur = head;//cur代跑 while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } } //从指定位置打印链表 public void display(ListNode newHead) { ListNode cur = newHead;//cur代跑 while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key) { ListNode cur = head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next; } return false; } //得到单链表的长度 public int size() { int count = 0; ListNode cur = head; while (cur != null) { count++; cur = cur.next; } return count; } // 无头单向非循环链表实现 //头插法 public void addFirst(int data) { ListNode node = new ListNode(data); node.next = head; head = node; } //尾插法 public void addLast(int data) { ListNode node = new ListNode(data); if (head == null) {//判空 head = node; return; } ListNode cur = head; while (cur.next != null) { cur = cur.next; } cur.next = node; } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int data) { checkIndex(index); if (index == 0) { addFirst(data);//头插法 return; } if (index == size()) { addLast(data);//尾插法 } ListNode cur = findIndexSubOne(index); ListNode node = new ListNode(data); node.next = cur.next; cur.next = node; } //找到index-1位置的节点的地址 private ListNode findIndexSubOne(int index) { ListNode cur = head; int count = 0; while (count != index - 1) { cur = cur.next; count++; } return cur; } private void checkIndex(int index) { if (index < 0 || index > size()) { throw new ListIndexOutOfException("index位置不合法"); } } //删除第一次出现关键字为key的节点 O(N) public void remove(int key) { if (head == null) { return;//1个节点都没有 } if (head.val == key) { head = head.next; return; } ListNode cur = searchPrev(key); if (cur == null) { return; } cur.next = cur.next.next; } //找到key的前一个节点 private ListNode searchPrev(int key) { ListNode cur = head; while (cur.next != null) {//为空 是最后一个节点 if (cur.next.val == key) {//cur是key的前一个节点 return cur; } cur = cur.next; } return null;//没有要删除的节点 } //删除所有值为key的节点 public void removeAllKey(int key) { if (head == null) { return; } ListNode prev = head; ListNode cur = head.next; while (cur != null) { if (cur.val == key) { prev.next = cur.next; //cur=cur.next; } else { prev = cur; //cur=cur.next; } cur = cur.next;//优化 } if (head.val == key) { head = head.next; } } //保证链表当中所有的节点都可以被回收 public void clear() { head = null; } public ListNode reverseList() { if (head == null) { return null; } //只有一个节点 if (head.next == null) { return head; } ListNode cur = head.next; head.next = null; while (cur != null) { ListNode curNext = cur.next;//提前记录下一个 cur.next = head; head = cur; cur = curNext; } return head; } //返回链表的中间节点 public ListNode middleNode(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } //链表倒数第k个节点 public ListNode findKthToTail(int k) { if (k <= 0 ||head==null) { return null; } ListNode fast = head; ListNode slow = head; /*for (int i = 0; i < k - 1; i++) { fast = fast.next; }*/ while(k-1!=0){ fast=fast.next; if(fast==null){ return null; } k--; } while (fast.next != null) { fast = fast.next; slow = slow.next; } return slow; } //链表的回文结构 //中间节点 翻转 public boolean chkPalindrome() { if(head==null){ return false; } if(head.next==null){ return true; } ListNode fast = head; ListNode slow = head; //slow为中间节点 while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } //翻转 ListNode cur=slow.next;//代表当前需要翻转的节点 while(cur!=null){ ListNode curNext=cur.next; cur.next=slow; slow=cur; cur=curNext; } //一个从头往后 一个从后往前 while(slow!=head){ if(head.val!=slow.val){ return false; } //偶数的情况 if(head.next==slow){ return true; } slow=slow.next; head=head.next; } return true; } }