Skip to content

Instantly share code, notes, and snippets.

@diaolizhi diaolizhi/LinkedList.java
Last active Oct 13, 2018

Embed
What would you like to do?
Java 链表
/**
* void deleteLast() 删除最后一个元素
* void delete(int k) 删除第 k 个元素
* boolean find(LinkedList list, String key) 查找链表中是否存在某个结点的值域为 key
* void removeAfter(Node node) 删除该结点的后续结点
* void insertAfter(Node node1, Node node2) 将第二个结点放在第一个结点后面
* void remove(LinkedList list, String key) 删除所有值为 key 的结点
* int max(LinkedList first) 接收一个首结点,返回值最大的结点的值,为空返回 0
* int max(LinkedList first) 用递归解决
*/
public class LinkedList<Item> {
private Node first;
class Node {
private Item item;
private Node next;
public Node() {
}
public Node(Item item) {
this.item = item;
this.next = null;
}
}
public LinkedList() {
first = null;
}
// 插入元素
public void add(Item item) {
Node newNode = new Node();
newNode.item = item;
if(isEmpty()) {
first = newNode;
return;
}
Node temp = first;
while(temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
// 插入元素,直接插入结点
public void add(Node newNode) {
if(first == null) {
first = newNode;
return;
}
Node temp = first;
while(first != null && temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
public boolean isEmpty() {
return first == null;
}
// 删除最后一个元素
// 涉及删除操作的,通常使用两个 Node
public void deleteLast() {
// 如果链表为空,就不用删除
if(isEmpty()) return;
// 如果只有一个元素,first 就指向 null
if(first.next == null) first = null;
// 使用两个元素,找到最后一个元素
Node before = first;
Node after = before.next;
while(after.next != null) {
before = after;
after = after.next;
}
before.next = null;
}
// 删除第 k 个元素
public void delete(int k) {
// 链表为空直接返回
if(isEmpty() || k < 1) return;
// 要删除第一个元素的话,first 指向 first.next
if(k == 1) {
first = first.next;
return;
}
// 排除以上两种情况之后,从第二个元素(after)开始对比 k
// 如果 i == k,before.next = after.next
Node before = first;
Node after = first.next;
for(int i = 2; i <= k && after != null; i++) {
if(i == k) {
before.next = after.next;
break;
}
before = after;
after = after.next;
}
}
// 查找链表中是否存在某个结点的值域为 key
// 泛型类非要指定一个类型,如果故意不按规则调用就会出错
public boolean find(LinkedList<Item> list, String key) {
Node temp = list.first;
while(temp != null) {
if(temp.item.equals(key)) {
return true;
}
temp = temp.next;
}
return false;
}
// 删除某个结点之后的结点
public void removeAfter(Node node) {
if(node == null || node.next == null) return;
Node temp = first;
while(temp != null) {
if(node == temp) {
break;
}
temp = temp.next;
}
// 到这一步,要么是 temp == node,要么是 temp == null
// 若是前者,temp.next = null,即可删除后面的元素。
if(temp != null) {
temp.next = null;
}
}
// 将第二个结点插入链表,并使之成为第一个结点的后续结点。node1 应该已经存在于链表
public void insertAfter(Node node1, Node node2) {
if(node1 == null || node2 == null) return;
Node temp = first;
while(temp != null) {
if(temp == node1) {
node2.next = node1.next;
node1.next = node2;
break;
}
temp = temp.next;
}
}
// 删除所有值为 key 的结点
public void remove(LinkedList<Item> list, String key) {
Node temp = first;
while(temp != null && temp.item.equals(key)) {
first = temp.next;
temp = first;
}
if(temp == null) return;
Node before = temp;
Node after = temp.next;
while(after != null) {
if(after.item.equals(key)) {
before.next = after.next;
after = after.next;
} else {
before = after;
after = after.next;
}
}
}
// 返回链表结点中最大的那个数字
public int max(LinkedList<Integer>.Node head) {
if(head == null) return 0;
int max = head.item;
head = head.next;
while(head != null) {
if(head.item > max) {
max = head.item;
}
head = head.next;
}
return max;
}
// 用递归解决
public int max2(LinkedList<Integer>.Node head) {
if(head == null) return 0;
if(head.next == null) return head.item;
int cur = head.item;
int oth = max2(head.next);
return cur > oth ? cur : oth;
}
public void display() {
Node temp = first;
while(temp != null) {
System.out.print(temp.item + " ");
temp = temp.next;
}
System.out.println();
}
/**
* 创建内部类对象必须创建外部类对象。
* @param key
* @return
*/
public Node getANode(Item key) {
return new Node(key);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.