统一使用的结点类：
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
-
反转链表（206. Reverse Linked List）
问题描述：给定一个单链表，将其反转。
//206.反转链表
public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode res=null;
while (curr != null) {
res=new ListNode(curr.val,res);
curr=curr.next;
}
return res;
}
解释：
使用一个临时节点res来构建反转后的链表。
遍历原链表，每次创建一个新节点，将其值设置为当前节点的值，并将新节点的next指针指向res。
更新res为新节点，继续遍历直到原链表结束。
返回res，即反转后的链表的头节点。 -
移除链表元素（203. Remove Linked List Elements）
问题描述：给定一个链表和一个值val，删除链表中所有值为val的节点，并返回新的链表。
解决方案：
//203.移除链表元素
public ListNode removeElements(ListNode head, int val) {
ListNode res = new ListNode(Integer.MIN_VALUE,head);
ListNode cur = res;
while (cur.next != null) {
if(cur.next.val == val){
cur.next = cur.next.next;
}else {
cur = cur.next;
}
}
return res.next;
}
}
解释：
使用一个哨兵节点res，其next指针指向原链表的头节点。
遍历链表，如果当前节点的下一个节点的值等于val，则跳过该节点。
否则，移动当前节点到下一个节点。
返回res.next，即新的链表的头节点。 -
设计链表（707. Design Linked List）
问题描述：设计一个支持以下操作的链表：
MyLinkedList()：初始化链表。
int get(int index)：获取链表中下标为index的节点的值。如果下标无效，则返回-1。
void addAtHead(int val)：将一个值为val的节点插入到链表中第一个元素之前。
void addAtTail(int val)：将一个值为val的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val)：将一个值为val的节点插入到链表中下标为index的节点之前。
void deleteAtIndex(int index)：如果下标有效，则删除链表中下标为index的节点。
解决方案：
//707.设计链表
class MyLinkedList {
ListNode head;
int size;
//MyLinkedList() 初始化 MyLinkedList 对象。
public MyLinkedList() {
this.head = new ListNode();
this.size = 0;
}
//int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
public int get(int index) {
if(index < 0 || index >= size) {
return -1;
}
int count = 0;
ListNode cur = head.next;//=========
while (cur != null) {
if (count == index) {
return cur.val;
}else {
cur = cur.next;
count++;
}
}
return -1;
}
//void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
public void addAtHead(int val) {
head.next = new ListNode(val, head.next);
size++;
}
//void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
public void addAtTail(int val) {
/if (size == 0) {
head.next = new ListNode(val);
}else {
ListNode last = getNode(size - 1);
if (last != null) {
last.next = new ListNode(val);
}
}
size++;/
ListNode newNode = new ListNode(val);
if (size == 0) {
// 链表为空，新节点直接成为头节点的下一个节点
head.next = newNode;
} else {
// 获取最后一个节点
ListNode lastNode = getNode(size - 1);
if (lastNode != null) {
lastNode.next = newNode;
}
}
size++;
}
//void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
// 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
public void addAtIndex(int index, int val) {
if(index<0 || index>size){
return;
}
if (indexsize){
addAtTail(val);
}else {
if(index0){
addAtHead(val);
}else {
ListNode cur = getNode(index - 1);
if (cur != null) {
cur.next = new ListNode(val, cur.next);
size++;
}
}
}
}
//void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
public void deleteAtIndex(int index) {
if(index<0 || index>=size){
return;
}
if(index0){
head.next = head.next.next;
//size--;
}else {
ListNode cur = getNode(index - 1);
if (cur != null) {
cur.next = cur.next.next;
}
}
size--;
}
private ListNode getNode(int index) {
if(index<0 || index>=size){
return null;
}
ListNode cur = head.next;//==
int count = 0;
while (cur != null) {
if (count == index) {
return cur;
}else {
cur = cur.next;
count++;
}
}
return null;
}
解释：
MyLinkedList构造方法：初始化一个哨兵节点head和链表的大小size。
get方法：获取链表中下标为index的节点的值。如果下标无效，则返回-1。
addAtHead方法：将一个值为val的节点插入到链表中第一个元素之前。
addAtTail方法：将一个值为val的节点追加到链表中作为链表的最后一个元素。
addAtIndex方法：将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，则该节点会被追加到链表的末尾。如果index比长度更大，则该节点将不会插入到链表中。
deleteAtIndex方法：如果下标有效，则删除链表中下标为index的节点。
getNode方法：返回索引位置的前一个节点，这样在addAtIndex和deleteAtIndex方法中可以直接使用返回的节点进行操作。