LC 206 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
这道题题的难点在于 如何移动指针的同时，将当前元素的next指向前驱元素；下面先介绍双指针写法
public ListNode reverseList(ListNode head) {
ListNode pre =null; //定义前驱节点
ListNode cur = head;//为了避免之后要操作链表的头节点，需要用一个变量来操作头节点指针，保持原来的头节点head不动
while(cur!=null){//循环终止条件为cur==null,此时前驱节点pre就是要返回的新链表的头节点
ListNode temp =cur.next;//同理 用一个临时变量先记录下当前节点的后继节点;为移动cur做准备
cur.next=pre;//将当前节点的next指向前驱节点,这是反转链表的关键
pre= cur;//移动pre指针
cur =temp;//移动cur到cur.next
}
return pre;
}
当要移动某个指针时候，先考虑当前指针指向的位置在之后的遍历中还需不需要用到，如果需要，直接拿个变量记住它就行了
在双指针的移动过程中，这里先移动pre，如果先移动cur到cur.next的话也可以，只不过要用个临时变量先把cur当前位置记录下来。
递归写法：
public ListNode reverseList(ListNode head) {
return reverse(head,null);
}
public static ListNode reverse(ListNode cur,ListNode pre){
if(cur==null) return pre;
ListNode temp = cur.next;
cur.next = pre;
return reverse(temp,cur);
}
递归我是这样理解的：一个reverse(cur,pre);相当于将当前cur的next指向pre，在其方法内部，有个临时变量temp记录了cur.next ，所以在回调reverse()函数时候，参数填充情况就变成了reverse(temp,cur);
LC.707 实现包括获取指定位置的元素，按下标插入新增节点，头插法增加节点，尾插法增加节点，以及删除指定位置的节点 方法在内的单链表
没什么好说的，需要注意的地方就是，将链表头节点定义为虚拟头节点，这个节点中的元素并不算入链表中
//单链表
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
}
class MyLinkedList {
//size存储链表元素的个数
int size;
//虚拟头结点
ListNode head;
//初始化链表
public MyLinkedList() {
size = 0;
head = new ListNode();
}
//获取第index个节点的数值
public int get(int index) {
//如果index非法，返回-1
if (index < 0 || index >= size) {
return -1;
}
ListNode currentNode = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode.val;
}
//在链表最前面插入一个节点
public void addAtHead(int val) {
addAtIndex(0, val);
}
//在链表的最后插入一个节点
public void addAtTail(int val) {
addAtIndex(size, val);
}
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
size++;
//找到要插入节点的前驱
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
//删除第index个节点
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
if (index == 0) {
head = head.next;
return;
}
ListNode pred = head;
for (int i = 0; i < index ; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}
}
LC.203 移除链表中的元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
定义虚拟头节点：那么无论是哪个位置的元素都可以正常移除，不定义虚拟头节点,直接将cur初始化为head，就需要考虑要删除的元素在0位置的情况，特殊处理。
定义虚拟头节点
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dumpyHead = new ListNode();
dumpyHead.next = head;
ListNode cur=dumpyHead;
while(cur!=null&&cur.next!=null){
if(cur.next.val==val){
cur.next=cur.next.next;
}else{
cur = cur.next;
}
}
return dumpyHead.next;
}
}
不定义虚拟头节点
class Solution {
public ListNode removeElements(ListNode head, int val) {
while(head!=null&&head.val==val){
head=head.next;
}
ListNode cur=head;
while(cur!=null&&cur.next!=null){
if(cur.next.val==val){
cur.next=cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
}