数据结构第一节之单链表，看完即可去刷题

数据结构第一节之单链表&＃xff0c;看完即可去刷题

下面的代码讲述了从创建到应用的过程。
//链表中节点的结构
class Node {
public int val;
public Node next;
public Node() {

}
public Node(int val) {this.val &＃61; val;
}


}
//链表的创建
public class MyLinkedList {

public Node head;//表示当前链表的头 默认是null/****/
public void createLinked() {this.head &＃61; new Node(12);Node node2 &＃61; new Node(22);Node node3 &＃61; new Node(32);Node node4 &＃61; new Node(42);this.head.next &＃61; node2;node2.next &＃61; node3;node3.next &＃61; node4;
}


//打印链表
public void display() {
Node cur &＃61; this.head;
while (cur !&＃61; null) {
System.out.print (cur.val &＃43;" ");
//
cur &＃61; cur.next;
}
System.out.println();
}

/*** 从指定的位置newHead* 开始进行打印* &＃64;param newHead*/
public void display(Node newHead) {Node cur &＃61; newHead;while (cur !&＃61; null) {System.out.print (cur.val &＃43;" ");cur &＃61; cur.next;}System.out.println();
}public Node findLastNode() {if(this.head &＃61;&＃61; null) {System.out.println("head &＃61;&＃61; null");return null;}Node cur &＃61; this.head;while (cur.next !&＃61; null) {cur &＃61; cur.next;}return cur;
}/*** 这个代码有瑕疵 改这个代码* &＃64;return*/
public Node findLastTwoNode() {if(this.head &＃61;&＃61; null) {System.out.println("想啥呢&＃xff0c;什么都没有&＃xff01;");return null;}if(this.head.next &＃61;&＃61; null) {System.out.println("想啥呢&＃xff0c;只有1个节点&＃xff01;");return null;}Node cur &＃61; this.head;while (cur.next.next !&＃61; null) {cur &＃61; cur.next;}return cur;
}public Node findN(int n) {if(this.head &＃61;&＃61; null) {System.out.println("单链表为空&＃xff01;");return null;}if(n <&＃61; 0) {System.out.println("n太小了&＃xff01;");return null;}if(n > size()) {System.out.println("n太大了");return null;}int count &＃61; 1;Node cur &＃61; this.head;while (count !&＃61; n) {count&＃43;&＃43;;//1cur &＃61; cur.next;}return cur;
}//得到单链表的长度
public int size(){Node cur &＃61; this.head;int count &＃61; 0;while (cur !&＃61; null) {count&＃43;&＃43;;//2cur &＃61; cur.next;}return count;
}//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {Node cur &＃61; this.head;while (cur !&＃61; null) {if(cur.val &＃61;&＃61; key) {return true;}cur &＃61; cur.next;}return false;
}//头插法
public void addFirst(int data) {//0、首先你得有个节点Node node &＃61; new Node(data);//1、判断链表是不是空的if(this.head &＃61;&＃61; null) {this.head &＃61; node;}else {//2、插入node.next &＃61; this.head;this.head &＃61; node;}//0、首先你得有个节点/* Node node &＃61; new Node(data);//1、判断链表是不是空的node.next &＃61; this.head;this.head &＃61; node;*/
}//尾插法
public void addLast(int data) {//0、newNode node &＃61; new Node(data);if(this.head &＃61;&＃61; null) {this.head &＃61; node;}else {//1、cur 找尾巴Node cur &＃61; this.head;while (cur.next !&＃61; null) {cur &＃61; cur.next;}//2、插入cur.next &＃61; node;}
}/*** 该函数是找到index-1位置的节点的引用* &＃64;param index* &＃64;return*/
public Node moveIndex(int index) {Node cur &＃61; this.head;int count &＃61; 0;while (count !&＃61; index-1) {cur &＃61; cur.next;count&＃43;&＃43;;}return cur;
}//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) {if(index <0 || index > size()) {System.out.println("index不合法");return;}//头插法if(index &＃61;&＃61; 0) {addFirst(data);return;}//尾插法if(index &＃61;&＃61; size()) {addLast(data);return;}Node cur &＃61; moveIndex(index);//cur保存的是 index-1位置的节点的引用Node node &＃61; new Node(data);node.next &＃61; cur.next;cur.next &＃61; node;
}/*** 找到关键key的前驱&＃xff0c;如果有返回前驱节点的引用* 如果没有返回null* &＃64;param key* &＃64;return*/
public Node searchPrev(int key) {Node cur &＃61; this.head;while (cur.next !&＃61; null) {if(cur.next.val &＃61;&＃61; key) {return cur;}cur &＃61; cur.next;}return null;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {if(this.head &＃61;&＃61; null) {return;}if(this.head.val &＃61;&＃61; key) {this.head &＃61; this.head.next;return;}Node prev &＃61; searchPrev(key);if(prev &＃61;&＃61; null) {System.out.println("没有这个key的前驱");}else {Node del &＃61; prev.next;prev.next &＃61; del.next;}
}
//删除所有值为key的节点
public void removeAllKey(int key){Node prev &＃61; this.head;Node cur &＃61; prev.next;while (cur !&＃61; null) {if(cur.val &＃61;&＃61; key) {prev.next &＃61; cur.next;}else {prev &＃61; cur;}cur &＃61; cur.next;}if(this.head.val &＃61;&＃61; key) {this.head &＃61; this.head.next;}
}public void clear() {this.head &＃61; null;
}


//翻转单链表
public Node reverseList() {
Node cur &＃61; this.head;
Node prev &＃61; null;
Node newHead &＃61; null;
while (cur !&＃61; null) {
Node curNext &＃61; cur.next;
if(curNext &＃61;&＃61; null) {
newHead &＃61; cur;
}
cur.next &＃61; prev;
prev &＃61; cur;
cur &＃61; curNext;
}
return newHead;
}

public Node reverseList2() {Node prev &＃61; null;while (head !&＃61; null) {Node cur &＃61; this.head;this.head &＃61; head.next;cur.next &＃61; prev;prev &＃61; cur;}return prev;
}
public Node reverseList3() {Node cur &＃61; this.head;Node prev &＃61; null;while (cur !&＃61; null) {Node curNext &＃61; cur.next;cur.next &＃61; prev;prev &＃61; cur;cur &＃61; curNext;}return prev;
}


//找到中间节点
public Node middleNode1() {
int len &＃61; size()/2;
Node cur &＃61; this.head;
int count &＃61; 0;
while (count !&＃61; len) {
cur &＃61; cur.next;
count&＃43;&＃43;;
}
return cur;
}

public Node middleNode() {Node fast &＃61; this.head;Node slow &＃61; this.head;while (fast !&＃61; null && fast.next !&＃61; null) {fast &＃61; fast.next.next;slow &＃61; slow.next;}return slow;
}


以上就是单链表的所有代码&＃xff0c;大家可根据此图来理解