目录
单向链表
双向链表
链表反转
删除链表中指定的所有值
单向链表
package basic.linkedList;
public class SingleNode {
public SingleNode next;
public int value;
public SingleNode(int value) {
this.value = value;
}
public static SingleNode reverseSingleNode(SingleNode head){
SingleNode next=null;
SingleNode pre=null;
while (head!=null){
next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
}
//删除链表中的值 要考虑删除的是头结点 或者是中间节点两种情况
public static SingleNode removeValue(SingleNode head,int num){
while (head!=null){//处理删除的值在头结点的情况
if (head.value==num){
head=head.next;
}else {
break;
}
}
//经过上面处理，head来到了第一个不需要删除的节点的位置
SingleNode pre=head;//用于维护一个节点的next值，辅助变量
SingleNode cur=head;
while (cur!=null){
if (cur.value==num){
pre.next = cur.next;
}else {
pre=cur;
}
cur=cur.next;
}
return head;
}
}
双向链表
package basic.linkedList;
public class DoubleNode {
public DoubleNode pre;
public DoubleNode next;
public int value;
public DoubleNode(int value) {
this.value = value;
}
public static DoubleNode reverseDoubleNode(DoubleNode head){
DoubleNode next=null;
DoubleNode pre=null;
while (head!=null){
next=head.next;
head.next=pre;
head.pre=next;
pre=head;
head=next;
}
return pre;
}
//删除链表中的值 要考虑删除的是头结点 或者是中间节点两种情况
public static DoubleNode removeValue(DoubleNode head,int num){
while (head!=null){//处理删除的值在头结点的情况
if (head.value==num){
head=head.next;
head.pre=null;
}else {
break;
}
}
//经过上面处理，head来到了第一个不需要删除的节点的位置
DoubleNode pre=head;//用于维护一个节点的next值，辅助变量
DoubleNode cur=head;
while (cur!=null){
if (cur.value==num){
pre.next = cur.next;
cur.next.pre=pre;
}else {
pre=cur;
}
cur=cur.next;
}
return head;
}
}
链表反转
链表反转就是先保存next和pre，然后再调整，与数值交换差不多。
package basic.linkedList;
/**
* 链表的指针反转
* 给定头结点，返回反转后的头结点
*/
public class ReverseList {
public static SingleNode reverseSingleNode(SingleNode head){
SingleNode next=null;
SingleNode pre=null;
while (head!=null){
next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
}
public static DoubleNode reverseDoubleNode(DoubleNode head){
DoubleNode next=null;
DoubleNode pre=null;
while (head!=null){
next=head.next;
head.next=pre;
head.pre=next;
pre=head;
head=next;
}
return pre;
}
}
删除链表中指定的所有值
删除链表中的值 要考虑删除的是头结点 或者是中间节点两种情况，剩下的就是链表指针的更改了
package basic.linkedList;
public class RemoveGivenValue {
//删除链表中的值 要考虑删除的是头结点 或者是中间节点两种情况
public static SingleNode removeValue(SingleNode head,int num){
while (head!=null){//处理删除的值在头结点的情况
if (head.value==num){
head=head.next;
}else {
break;
}
}
//经过上面处理，head来到了第一个不需要删除的节点的位置
SingleNode pre=head;//用于维护一个节点的next值，辅助变量
SingleNode cur=head;
while (cur!=null){
if (cur.value==num){
pre.next = cur.next;
}else {
pre=cur;
}
cur=cur.next;
}
return head;
}
//删除链表中的值 要考虑删除的是头结点 或者是中间节点两种情况
public static DoubleNode removeValue(DoubleNode head,int num){
while (head!=null){//处理删除的值在头结点的情况
if (head.value==num){
head=head.next;
head.pre=null;
}else {
break;
}
}
//经过上面处理，head来到了第一个不需要删除的节点的位置
DoubleNode pre=head;//用于维护一个节点的next值，辅助变量
DoubleNode cur=head;
while (cur!=null){
if (cur.value==num){
pre.next = cur.next;
cur.next.pre=pre;
}else {
pre=cur;
}
cur=cur.next;
}
return head;
}
}
