反转单链表
1、 next抓住下一个结点；
2、 当前节点的next指针指向pre；
3、 pre指针指向当前节点；
4、 当前节点指针执行next；
5、 下一个循环；
/**
* 反转单链表
*/
public class List01 {
public static class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
public static Node reverse(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.next; // 保存当前head节点的后继节点
head.next = pre; // head的后继指针指向pre节点
pre = head; // 保存当前head节点的引用到pre
head = next; // head指向下一个节点
}
// head指向null，跳出了循环，此时pre就是原来的尾结点，反转后的新头部节点
return pre;
}
}
反转双向链表
1、 next抓住下一个结点；
2、 修改当前结点的next指针和last指针的指向；
3、 pre指针执行当前结点；
4、 当前结点指向next；
5、 下一个循环；
/**
* 反转双向链表
*/
public class List02 {
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
public static DoubleNode reverse(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next; //保存head的下一个节点
head.last = next; //修改head的last指针指向原next节点
head.next = pre; //修改head的next指针指向原pre指针
pre = head; //当前head节点赋值给pre
head = next; //遍历下一个节点
}
return pre;
}
}
删除链表中指定的数的节点
一个pre指针
一个cur指针
如果cur指针指向的节点的值是要删除的值
则pre的next指针指向cur的next指针指向的节点
然后pre不动，cur指向下一个节点
如果cur指针指向的节点的值不是要删除的值，则pre指向cur，cur指向cur.next
但是要注意，有可能链表头部，或者头部的几个节点，都是要删除的，所以要先跳过所有要删除的头部，并且最后要返回一个新头部
/**
* 删除链表中指定的数的节点
*/
public class List03 {
public static class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
public static Node reverse(Node head, int num) {
//如果头节点的值为给定的值，则一直删除，直到与给定值不等
while (head != null && head.value == num) {
head = head.next;
}
//此时的head的value必然与num不等
Node pre = null;
Node cur = null;
while (cur != null) {
if (cur.value == num) {
// 如果当前结点的value是要删除的之，则pre的next指针指向cur的next
pre.next = cur.next;
} else {
// 否则pre指向cur，下一此循环用
pre = cur;
}
cur = cur.next;
}
return head;
}
}