一、单链表和双链表反转
public class ReverseNode {
public static class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int value) {
this.value = value;
}
}
public static Node reverseNode(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
public static DoubleNode reverseDoubleNode(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}
}
核心点：
（1）单链表：
拿到next节点，修改当前节点的next节点，拿到pre节点，当前节点后移
（2）双链表：
拿到next节点，修改当前节点的next、last节点，拿到pre节点，当前节点后移
二、单链表删除指定的值
public class DeleteNodeValue {
public static class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
public static Node removeValue(Node head, int num) {
while (head != null) {
if (head.value != num) {
break;
}
head = head.next;
}
Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}
}
核心点：
1）找到不需要删除值的节点作为头节点（最后返回此头节点）
2）标记pre和cur节点
3）从cur开始挨个遍历剩下的节点
如果cur节点的值等于要删除的值，则修改pre节点的next节点；
如果cur节点的值不是要删除的值，则将pre节点修改为cur节点。
|