基础知识：
203.移除链表元素
建议： 本题最关键是要理解 虚拟头结点的使用技巧，这个对链表题目很重要。
这里主要记录用虚头的方法。即设置一个虚拟的头指针帮忙解题。
先看代码：
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy=new ListNode();
dummy.next=head;
ListNode curr=dummy;
while(curr.next!=null)
{
if (curr.next.val==val)
{
curr.next=curr.next.next;
}
else
{
curr=curr.next;
}
}
return dummy.next;
}
}这样做有一个很明确的目的：因为我们是通过前一个节点来判断后一个节点是否该删除，但是头节点没有前一个节点，所以我们可以虚拟一个新的头节点，这样真实的头节点也有了头节点，我们的代码就不需要写一个if来判断是否为头节点这种情况。
707.设计链表
这个其实可以当作对刚才所学的一个复习，实现可以分为单指针和双指针
以下为单链表：
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
size=0;
head=new ListNode(0);
}
public int get(int index) {
if (index<0||index>=size)
{
return -1;
}
ListNode curr=head;
for (int i=0;i<=index;i++)
{
curr=curr.next;
}
return curr.val;
}
public void addAtHead(int val) {
ListNode newNode=new ListNode(val);
newNode.next=head.next;
head.next=newNode;
size++;
}
public void addAtTail(int val) {
ListNode newNode=new ListNode(val);
ListNode curr=head;
while (curr.next!=null)
{
curr=curr.next;
}
curr.next=newNode;
size++;
}
public void addAtIndex(int index, int val) {
if (index>size)
{
return;
}
if (index<0)
{index=0;}
size++;
ListNode newNode=new ListNode(val);
ListNode curr=head;
for (int i=0;i<index;i++)//要在该索引的位置前一个索引才对
{
curr=curr.next;
}
newNode.next=curr.next;
curr.next=newNode;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
ListNode curr=head;
for (int i = 0; i < index ; i++) {
curr = curr.next;
}
curr.next=curr.next.next;
}
}
以下为双链表：
//双链表
class ListNode{
int val;
ListNode next,prev;
ListNode() {};
ListNode(int val){
this.val = val;
}
}
class MyLinkedList {
//记录链表中元素的数量
int size;
//记录链表的虚拟头结点和尾结点
ListNode head,tail;
public MyLinkedList() {
//初始化操作
this.size = 0;
this.head = new ListNode(0);
this.tail = new ListNode(0);
//这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
head.next=tail;
tail.prev=head;
}
public int get(int index) {
//判断index是否有效
if(index>=size){
return -1;
}
ListNode cur = this.head;
//判断是哪一边遍历时间更短
if(index >= size / 2){
//tail开始
cur = tail;
for(int i=0; i< size-index; i++){
cur = cur.prev;
}
}else{
for(int i=0; i<= index; i++){
cur = cur.next;
}
}
return cur.val;
}
public void addAtHead(int val) {
//等价于在第0个元素前添加
addAtIndex(0,val);
}
public void addAtTail(int val) {
//等价于在最后一个元素(null)前添加
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
//index大于链表长度
if(index>size){
return;
}
size++;
//找到前驱
ListNode pre = this.head;
for(int i=0; i<index; i++){
pre = pre.next;
}
//新建结点
ListNode newNode = new ListNode(val);
newNode.next = pre.next;
pre.next.prev = newNode;
newNode.prev = pre;
pre.next = newNode;
}
public void deleteAtIndex(int index) {
//判断索引是否有效
if(index>=size){
return;
}
//删除操作
size--;
ListNode pre = this.head;
for(int i=0; i<index; i++){
pre = pre.next;
}
pre.next.next.prev = pre;
pre.next = pre.next.next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/206.反转链表
有两种写法
第一种：双指针
通过循环和两个指针把链表的指向全部反转过来。
加入temp指针的目的是保存cur的next值，这样在你把cur.next赋值给prev时，这个值不会丢失，然后更新变量进入下一个循环
public ListNode reverseList(ListNode head) {
ListNode cur=head;
ListNode prev=null;
ListNode temp=null;
while(cur!=null)
{
temp=cur.next;
cur.next=prev;
prev=cur;
cur=temp;
}
return prev;
}
}第二种：递归
其实递归和这个双指针写法是一样一样的，只要理解了双指针解法，该方法非常好理解并且简单。
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
public ListNode reverse(ListNode prev,ListNode cur)
{
if (cur==null)
{
return prev;
}
ListNode temp=null;
temp=cur.next;
cur.next=prev;
// 更新prev、cur位置
// prev = cur;
// cur = temp;
return reverse(cur,temp);
}
}