创建节点

    public class Node {T val;Node next;public Node(T val, Node next) {this.val = val;this.next = next;}public Node() {this(null, null);}public Node(T val) {this(val, null);}} 

创建一个空链表

    //创建链表public Node header;private int size;public MyLinkedList() {this.header = null;this.size = 0;}

数据存储在节点中。
优点：不需要处理固态容量问题，可动态扩容。
缺点：丧失随机访问的能力。

添加元素

表头添加元素

    //表头添加元素public void addHead(T val) {Node cur = new Node(val, null);cur.next = header;header = cur;this.size++;}

表尾添加元素

    //表尾添加元素public void addTail(T val) {Node cur = new Node(val, null);Node p = header;while (p != null) {p = p.next;}p.next = cur;this.size++;}

表任意位置添加元素

    public void add(int index, T val) {if (index < 0 || index > size) {throw new IllegalArgumentException("index is invalid!");}// 创建新结点Node node = new Node(val);// 1、先找pre//需要对头结点做特殊处理，原因是头结点没有pre(前驱结点)/* 添加虚拟头结点，保证链表中所有的结点都有pre*/Node dummyHeader = new Node(null, this.header);Node pre = dummyHeader;for (int i = 1; i <= index; i++) {pre = pre.next;}//2、、挂接node.next = pre.next;pre.next = node;//3、 更新头结点this.header = dummyHeader.next;// 3、更新sizethis.size++;} 

删除元素

    public void delete(int index){if(index<0||index>this.size)return ;Node pre=this.header;int cnt=0;while(index!=cnt){cnt++;pre=pre.next;}Node cur=pre.next;pre.next=cur.next;cur.next=null;}  

遍历链表

    @Overridepublic String toString() {ArrayList<T> list = new ArrayList<>();Node cur = this.header;while (cur != null) {list.add(cur.val);cur = cur.next;}StringBuilder sb = new StringBuilder();for (T x : list) {sb.append(x + "--->");}sb.append("Null");return sb.toString();}

查询元素是否存在

    //查询元素在链表中是否存在public boolean contains(T val){Node pre=this.header;while(pre!=null){if(pre.val.equals(val))return true;else pre=pre.next;}return false;}  

力扣例题

剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode）

https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/

顺序查找

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {public ListNode getKthFromEnd(ListNode head, int k) {ListNode pre=head,cur=head;int len=0;while(pre!=null){len++;pre=pre.next;}int cnt=0;while(len-k!=cnt){cnt++;cur=cur.next;}return cur;}
}

快慢指针

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode getKthFromEnd(ListNode head, int k) {ListNode fast=head;ListNode slow=head;while(k>0&&fast!=null){fast=fast.next;k--;}while(fast!=null){slow=slow.next;fast=fast.next;}return slow;}
}

两两交换链表中的节点 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

创建虚拟头节点，疯狂迭代

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {ListNode dummyhead=new ListNode(0);dummyhead.next=head;ListNode temp=dummyhead;while(temp.next!=null&&temp.next.next!=null){ListNode node1=temp.next;ListNode node2=temp.next.next;node1.next=node2.next;node2.next=node1;temp.next=node2;temp=node1;}return dummyhead.next;}
}

递归（♂♂♂）

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if(head==null||head.next==null)return head;ListNode pre=head.next;head.next=swapPairs(pre.next);pre.next=head;return pre;}
}

反转链表 II - 力扣（LeetCode）

合并两个有序链表 - 力扣（LeetCode）

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1==null)return list2;if(list2==null)return list1;if(list1.val>list2.val){list2.next=mergeTwoLists(list2.next,list1);return list2;}else{list1.next=mergeTwoLists(list1.next,list2);return list1;}}
}

反转链表 - 力扣（LeetCode）

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode pre=null;ListNode node=head;while (node!=null){ListNode next=node.next;node.next=pre;pre=node;node=next;}return pre;}
}