链表的基本操作

链表的分类

单向/双向（引入了 prev 引用）
带傀儡节点/不带傀儡节点（dummy node）
带环/不带环

链表的遍历

遍历方式可利用 while 或者 for 循环来进行实现，主要代码块可展示为：

//for循环实现
for(Node cur = head; cur != null; cur = cur.next){....
}
//while循环实现
Node cur = head;
while（cur != null){....cur = cur.next;
}

1.遍历不带傀儡节点的链表

//遍历 不带傀儡节点的链表public static void print(Node head){for(Node cur = head; cur != null; cur= cur.next){System.out.println(cur.val);}}

2.遍历带傀儡节点的链表

//遍历 带傀儡节点的链表public static void printWithDummy(Node head){for(Node cur = head.next; cur != null; cur = cur.next){System.out.println(cur.val);}}

链表元素的插入

元素插入链表头部
元素插入链表中部
元素插入链表尾部

1.插入头部位置和中间位置

2.插入尾部位置

一般情况下尾部插入一个节点的相关代码如下：

//尾插一个节点public static void insertTail(Node head,int val){if(head == null){return;}// 1)找到末尾节点Node prev = head;while(prev != null){prev = prev.next;}//循环结束的时候，cur 就是最后一个节点Node newNode = new Node(val);newNode.next = prev.next;prev.next = newNode;}

当链表本身为空链表时，要实现插入元素，就需要借助方法的返回值/成员变量来实现，相关代码如下：

//insertTail方法
public static Node insertTail(Node head,int val){Node newNode = new Node(val);if(head == null){return newNode;}Node prev = head;while(prev.next != null){prev = prev.next;}newNode.next = prev.next;prev.next = newNode;return head;
}//main函数
public static void main(String[] args) {
Node head = null;
head = insertTail(head,val:100);
print(head);
}

链表元素的删除

删除一般节点
删除头节点（需更改 head 的指向）
1.删除一般节点一般有三种方法：一种是按待删除节点的值进行删除；一种是按待删除节点的位置进行删除；一种是按节点下标进行删除

   //删除节点-按值删除public static void remove1(Node head,int value){// 1)找 val 对应的位置，同时找到 val 前一个位置Node prev = head;while(prev != null&& prev.next != null&& prev.next.val != value){prev = prev.next;}// 2)循环结束，prev 指向待删除的前一个节点if(prev == null || prev.next == null){//未找到值为 val 的节点return;}// 3)删除这个节点 toDelete 指向待删除节点Node toDelete = prev.next;prev.next = toDelete.next;}//删除节点-按位置删除public static void remove2(Node head,Node toDelete){// 1.找到 toDelete 前一个节点Node prev = head;while(prev != null && prev.next != toDelete){prev = prev.next;}if(prev == null){//没找到return;}// 2.进行删除prev.next = toDelete.next;}//按照 节点下标 进行删除public static int size(Node head){int size = 0;for(Node cur = head; cur != null; cur = cur.next){size++;}return size;}public static void remove3(Node head,int index){if(index < 0 || index >= size(head)){return;}if(index == 0){//TODO}// 1.找到待删除节点前一个的位置:即 index-1Node prev = head;for(int i = 0;i < index -1; i++){prev = prev.next;}//循环结束之后，prev 指向待删除节点的前一个位置// 2.进行删除操作Node toDelete = prev.next;prev.next = toDelete.next;}

2.“移花接木”删除节点
不涉及链表的遍历，直接将待删除节点之后的节点复制到待删除节点处
缺点：无法删除最后一个节点

  //“移花接木”删除节点public static void remove4(Node head,Node toDelete){Node nextNode = toDelete.next;toDelete.val = nextNode.val;toDelete.next = nextNode.next;}