单向链表题（Java）

不知名的忻

357人浏览 · 2025-12-09 22:16:09

不知名的忻 · 2025-12-09 22:16:09 发布

一、代码要素：

1.节点类

public static class ListNode{

        int value;
        ListNode next;

        public ListNode(int value,ListNode next) {
            this.value = value;
            this.next = next;
        }
    }

2.创建链表（fanhu）

①代码创建

// s -> 1->2->3->6->5->6->8->null
    public static ListNode createList(){
        ListNode n7=new ListNode(8,null);
        ListNode n6=new ListNode(6,n7);
        ListNode n5=new ListNode(5,n6);
        ListNode n4=new ListNode(6,n5);
        ListNode n3=new ListNode(3,n4);
        ListNode n2=new ListNode(2,n3);
        ListNode n1=new ListNode(1,n2);
        return n1;
    }

②控制台输入

replace用来把输入的 "[" "]" 替换成 "" 空白

split(",")用来将数字分离开来存入数组

Integer.parseInt(list[i])用来字符串转整数

public static ListNode creatList(){
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入一个链表（如：[1,2,3,4,5,6]）：");
        String input=sc.nextLine();
        input=input.replace(" ","")
                   .replace("[",",")
                   .replace("]",",");
        String[] list=input.split(",");
        ListNode head=null;
        for(int i=list.length-1;i>=0;i--){
            if (!list[i].isEmpty()){
                head=new ListNode(Integer.parseInt(list[i]),head);
            }
        }
        return head;
    }

3.打印链表

public static void printList(ListNode head){
        ListNode p=head;
        System.out.print("[");
        while(p!=null){
            System.out.print(p.value+",");
            p=p.next;
        }
        System.out.print("null]");
        System.out.println();
    }

4.main测试类

easy

5.反转、删除链表

①原地反转链表

pre	cur	n
s=null	1	2	3	4	5

之后pre和cur都往后移

1->2->3->4->5->null

null <- 1->2->3->4->5->null

null <- 1 <- 2->3->4->5->null

//3反转链表
    public static ListNode reverseList(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            //存
            ListNode n=cur.next;
            //指
            cur.next=pre;
            //换
            pre=cur;
            cur=n;
        }
        return pre;
    }

②根据指定的值value删除节点

原链表：1->2->3->6->5->6->8->null
输入要删除的值的节点：6
删除后的链表：1->2->3->5->8->null

p1 p2

s 1->2->3->6->5->6->8->null

如果遇到要删除的值就把p2右移，p1不变。

如果不要删除就把p1和p2都往右移。

public static ListNode removeNode(ListNode head,int value){
        s.next=head;
        ListNode p1=s;
        ListNode p2=s.next;
        while(p2!=null){
            if(p2.value==value){
                p1.next=p2.next;
                p2=p2.next;
            }
            else{
                p1=p2;
                p2 = p2.next;
            }
            

        }
        return s.next;
    }

③删除倒数位置的节点

1，2，3，4，5，6
e.g. 输入n=2,则删除5

/*
这个方法巧妙在于
1.p1和p2初始化为哨兵节点s
2.p2向右移动n+1次
3.p1和p2同时向右移动至p2=null
此时巧妙的地方就是p1在倒数第n+1的位置处
这里不是直接让p1指向倒数第n项，而是指向了前面的一项，这样才能保证能够表示处倒数n和n-1,也就是表示出4和5，方便删除4
* */

public static ListNode removeList(ListNode head, int n){
        ListNode s=new ListNode(-1,head);
        ListNode p1=s;
        ListNode p2=s;
        for (int i = 0; i < n+1; i++) {
            p2=p2.next;
        }
        while(p2!=null){
            p1=p1.next;
            p2=p2.next;
        }
        p1.next=p1.next.next;
        return s.next;
    }

④去重保留一个

//4.1.去重保留一个
    public static ListNode deleteList1(ListNode head){
        ListNode p1=head;
        ListNode p2=head.next;
        while(p2.next!=null){
            if(p1.value==p2.value){
                p1.next=p2.next;
                p2=p2.next;
            }
            else{
                p1=p2;
                p2=p2.next;
            }
        }
        return head;
    }

⑤去重全删

//4.1:去重全删
    //      [1,1,1,2,2,3,4,4,5]
    public static ListNode deleteList1(ListNode head){
        ListNode s=new ListNode(-1,head);
        if(head==null||head.next==null){
            return head;
        }
        ListNode p1=s;
        ListNode p2=head;
        ListNode p3=head.next;
        while(p2!=null&&p3!=null){
            if(p2.value==p3.value){
                p3=p3.next;
                while(p3!=null&&p2.value==p3.value){
                    p3=p3.next;
                }
                p1.next=p3;
                p2=p3;
                if(p3!=null){
                    p3=p3.next;
                }
            }else{
                p1=p2;
                p2=p3;
                if(p3!=null){
                    p3=p3.next;
                }
            }
        }
        return s.next;
    }

二、完整代码

1.原地反转链表

package com.JQ.SingleLinkedList;

import java.util.List;
import java.util.Scanner;

//反转链表
public class ReverseList {

    //1节点类
    static class ListNode{
        int value;
        ListNode next;
        public ListNode(int value,ListNode next){
            this.value=value;
            this.next=next;
        }
    }
    //2创建链表
    public static ListNode creatList(){
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入一个链表（如：[1,2,3,4,5,6]）：");
        String input=sc.nextLine();
        input=input.replace(" ","")
                   .replace("[",",")
                   .replace("]",",");
        String[] list=input.split(",");
        ListNode head=null;
        for(int i=list.length-1;i>=0;i--){
            if (!list[i].isEmpty()){
                head=new ListNode(Integer.parseInt(list[i]),head);
            }
        }
        return head;
    }
    //3打印链表
    public static void printList(ListNode head){
        while (head!=null){
            System.out.print(head.value+"->");
            head=head.next;
        }
    }
    //4反转链表
    public static ListNode reverseList(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            //存
            ListNode n=cur.next;
            //指
            cur.next=pre;
            //换
            pre=cur;
            cur=n;
        }
        return pre;

    }
    //5测试类
    public static void main(String[] args) {
        ReverseList r=new ReverseList();
        ListNode head=creatList();
        System.out.print("原链表：");
        printList(head);
        System.out.print("null");
        System.out.println();
        System.out.print("反转链表：");
        printList(reverseList(head));
        System.out.print("null");
    }
}

2.根据指定的值value删除节点

package com.JQ.SingleLinkedList;

import java.util.Scanner;

//根据值删除节点
public class RemoveList1 {
    //哨兵节点
    static ListNode s=new ListNode(-1,null);

    //1节点类
    public static class ListNode{

        int value;
        ListNode next;

        public ListNode(int value,ListNode next) {
            this.value = value;
            this.next = next;
        }
    }
    //2创建链表
    // s -> 1->2->3->6->5->6->8->null
    public static ListNode createList(){
        ListNode n7=new ListNode(8,null);
        ListNode n6=new ListNode(6,n7);
        ListNode n5=new ListNode(5,n6);
        ListNode n4=new ListNode(6,n5);
        ListNode n3=new ListNode(3,n4);
        ListNode n2=new ListNode(2,n3);
        ListNode n1=new ListNode(1,n2);
        return n1;
    }

    //3打印链表
    public static void printList(ListNode head){
        while(head!=null){
            System.out.print(head.value+"->");
            head=head.next;
        }
        System.out.print("null");
        System.out.println();
    }
    //4删除节点
    public static ListNode removeNode(ListNode head,int value){
        s.next=head;
        ListNode p1=s;
        ListNode p2=s.next;
        while(p2!=null){
            if(p2.value==value){
                p1.next=p2.next;
                p2=p2.next;
            }
            else{
                p1=p2;
                p2 = p2.next;
            }


        }
        return s.next;
    }
    //5测试类
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        ListNode head=createList();
        System.out.print("原链表：");
        printList(head);
        System.out.print("输入要删除的值的节点：");
        int value=sc.nextInt();
        System.out.print("删除后的链表：");
        printList(removeNode(head,value));
    }
}

3.删除倒数位置的节点

package com.JQ.SingleLinkedList;

import java.util.Scanner;

//P77集
//删除倒数位置的节点
//1，2，3，4，5，6，
//e.g. 输入n=2,则删除5
/*
这个方法巧妙在于
1.p1和p2初始化为哨兵节点s
2.p2向右移动n+1次
3.p1和p2同时向右移动至p2=null
此时巧妙的地方就是p1在倒数第n+1的位置处
* */
public class RemoveList2 {

    //1节点类
    public static class ListNode{
        ListNode next;
        int value;

        public ListNode( int value,ListNode next) {
            this.next = next;
            this.value = value;
        }
    }
    //2打印链表
    public static void printList(ListNode head){
        ListNode p=head;
        System.out.print("[");
        while(p!=null){
            System.out.print(p.value+",");
            p=p.next;
        }
        System.out.print("null]");
        System.out.println();
    }
    //3删除链表
    public static ListNode removeList(ListNode head, int n){
        ListNode s=new ListNode(-1,head);
        ListNode p1=s;
        ListNode p2=s;
        for (int i = 0; i < n+1; i++) {
            p2=p2.next;
        }
        while(p2!=null){
            p1=p1.next;
            p2=p2.next;
        }
        p1.next=p1.next.next;
        return s.next;
    }
    //4创建链表
    public static ListNode createList(){
        ListNode n5=new ListNode(5,null);
        ListNode n4=new ListNode(4,n5);
        ListNode n3=new ListNode(3,n4);
        ListNode n2=new ListNode(2,n3);
        ListNode n1=new ListNode(1,n2);
        return n1;
    }
    //5测试类
    public static void main(String[] args) {
        ListNode head=createList();
        System.out.print("原链表：");
        printList(head);
        Scanner sc=new Scanner(System.in);
        System.out.print("输入要删除倒数第n项的n的值：");
        int n=sc.nextInt();
        ListNode newhead=removeList(head,n);
        System.out.print("删除后的链表：");
        printList(newhead);
    }
}