java：单链表基础操作：插入、删除、移动节点

java：单链表基础操作：插入、删除、移动节点

1 前言

在Java中实现单链表插入节点，需根据插入位置（头部、尾部、中间）设计逻辑。同时探讨单链表的节点删除、移动操作。

2 使用

2.1 单链表

2.1.1 定义单链表节点类，并实现链表节点插入

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

单链表的插入操作定义：

public class SingleLinkedList {

    ListNode head;

    /**
     * 头插法
     */
    public void insertHead(int val) {
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
    }

    /**
     * 尾插法
     */
    public void insertTail(int val) {
        ListNode node = new ListNode(val);
        if (head == null) {
            head = node;
            return;
        }
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = node;
    }

    /**
     * 按照索引值，指定位置插入节点
     */
    public void insertWithIndex(int pos, int val) {
        if (pos < 0)
            throw new IllegalArgumentException("索引值错误，不能小于0.");

        if (pos == 0) {
            insertHead(val);
            return;
        }

        ListNode node = new ListNode(val);
        ListNode current = head;
        if(current == null) {
            head = node;
            return;
        }
        for (int i = 0; current.next != null && i < pos - 1; i++) {
            current = current.next;
        }
        node.next = current.next;
        current.next = node;
    }

    public void print() {
        ListNode current = head;
        System.out.println("打印链表节点数据：");
        if(current != null) {
            System.out.print(current.val);
            while (current.next != null) {
                System.out.print("=>" + current.next.val);
                current = current.next;
            }
            System.out.println("打印链表节点结束。");
        }
    }

}

• ‌头部插入‌：创建新节点，将其指向当前头节点，然后更新头节点为新节点。
• ‌尾部插入‌：遍历到链表末尾，将末尾节点的next指向新节点。
• ‌指定位置插入‌： 处理索引为0的情况，直接调用头部插入。 遍历到目标位置的前一个节点，调整指针将新节点插入。

测试类：

public class TestSingleLinkedList {

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.insertHead(9);
        singleLinkedList.insertHead(1);
        singleLinkedList.insertTail(4);
        singleLinkedList.insertWithIndex(2, 7);
        singleLinkedList.print();
    }

}

执行结果如下：

打印链表节点数据：
1=>9=>7=>4打印链表节点结束。

例子：

public static void main(String[] args) {
    SingleLinkedList singleLinkedList = new SingleLinkedList();
    singleLinkedList.insertWithIndex(6, 6);
    singleLinkedList.print();
}

执行结果如下：

打印链表节点数据：
6打印链表节点结束。

再举个例子：

public static void main(String[] args) {
    SingleLinkedList singleLinkedList = new SingleLinkedList();
    singleLinkedList.insertWithIndex(6, 6);
    singleLinkedList.insertWithIndex(6, 9);
    singleLinkedList.print();
}

结果如下：

打印链表节点数据：
6=>9打印链表节点结束。

• ‌边界条件‌：插入位置为0或链表末尾时需特殊处理。
• ‌异常处理‌：当索引无效时（如负数或超出长度），抛出异常确保程序健壮性。
• ‌时间复杂度‌：头部插入为O(1)，尾部和指定位置插入为O(n)。
• 空间复杂度‌：头部插入（只需创建一个新节点，并修改指针指向。无论链表多长，‌额外内存占用恒定‌，仅一个新节点和固定数量的临时指针）为O(1)，尾部和指定位置插入（虽然需要遍历链表找到尾部（时间复杂度 O(n)），但‌空间占用仅为一个新节点和一个临时指针‌（如 current），与链表长度无关）为O(1)。

2.1.2 如何优化上述的单链表节点插入操作？

在 Java 链表的操作中，‌哨兵节点（Sentinel Node）‌ 是一种简化边界条件处理的技巧，常用于避免对头节点（head）进行特殊判断。

‌哨兵节点的核心作用‌

• ‌统一操作逻辑‌

无论链表是否为空，添加或删除节点时都可以用相同的代码逻辑处理，避免对 head == null 的特殊判断。

• ‌简化头节点的修改‌

当需要修改头节点时（如插入或删除头节点），无需单独处理头指针的变化，只需通过哨兵节点的 next 指针操作。

• ‌防止空指针异常‌

在处理空链表时，哨兵节点作为占位符，确保代码不会因操作 null 而崩溃。

public class NewSingleLinkedList {

    ListNode head;

    /**
     * @param val 头插法，节点值
     */
    public void insertHead(int val) {
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
    }

    /**
     * @param val 尾插法，节点值
     */
    public void insertTail(int val) {
        ListNode node = new ListNode(val);
        ListNode sentry = new ListNode(-99);
        sentry.next = head;

        ListNode current = sentry;

        int i = 0;
        for(; current.next != null; i++) {
            current = current.next;
        }
        current.next = node;
        head = sentry.next;
    }

    /**
     * @param pos 按照索引值，指定插入的位置
     * @param val 插入的链表节点值
     */
    public void insertWithIndex(int pos, int val) {
        if(pos < 0)
            throw new IllegalArgumentException("索引值不能小于0.");

        ListNode node = new ListNode(val);
        ListNode sentryNode = new ListNode(-99);
        sentryNode.next = head;

        ListNode current = sentryNode;
        int i = 0;
        for(; current.next != null && i < pos; i++) {
            current = current.next;
        }
        node.next = current.next;
        current.next = node;
        head = sentryNode.next;
    }


    public void print(){
        ListNode current = head;
        System.out.println("打印链表节点数据：");
        if(current != null) {
            System.out.print(current.val);
            while (current.next != null) {
                System.out.print("=>" + current.next.val);
                current = current.next;
            }
            System.out.println("打印链表节点结束。");
        }
    }

}

public class TestNewSingleLinkedList {

    public static void main(String[] args) {
        NewSingleLinkedList singleLinkedList = new NewSingleLinkedList();
        singleLinkedList.insertHead(9);
        singleLinkedList.insertHead(1);
        singleLinkedList.insertTail(4);
        singleLinkedList.insertWithIndex(2, 7);
        singleLinkedList.insertWithIndex(0, 8);
        singleLinkedList.insertWithIndex(8, 5);
        singleLinkedList.print();
    }

}

结果如下：

打印链表节点数据：
8=>1=>9=>7=>4=>5打印链表节点结束。

‌哨兵节点的优缺点‌

• ‌优点‌

代码简洁，减少边界条件判断。
提高可读性和可维护性。

• ‌缺点‌

轻微的内存开销（多一个节点）。
需注意返回结果时跳过哨兵节点（如返回 sentinel.next）。

2.2.1 实现单链表节点删除

思路：

• ‌删除头节点‌：

检查链表是否为空，若为空则直接返回。
将头节点指向当前头节点的下一个节点。

• ‌删除尾节点‌：

检查链表是否为空，若为空则返回。
若链表只有一个节点，则将头节点置空。
遍历链表直到倒数第二个节点，将其next指针置空。

上述即，如果需要删除链表节点，删除单链表头结点，只需要将头节点head指向头结点的下一个节点，即head.next，时间复杂度为O(1)；如果是删除单链表的尾结点，需要遍历链表，找到尾结点的前驱结点，将前驱结点prev.next指向tail.next即可，时间复杂度为O(n)。

public class DeleteSingleLinkedList extends NewSingleLinkedList{

    /**
     * 删除单链表头节点
     */
    public void deleteHead() {
        if(head == null) return;
        head = head.next;
    }

    /**
     * 删除单链表尾结点
     */
    public void deleteTail() {
        if(head == null || head.next == null) {
            head = null;
            return;
        }

        ListNode prev = head;
        while(prev.next.next != null) {
            prev = prev.next;
        }
        prev.next = null;
    }

    public static void main(String[] args) {
        DeleteSingleLinkedList deleteSingleLinkedList = new DeleteSingleLinkedList();
        deleteSingleLinkedList.insertHead(4);
        deleteSingleLinkedList.insertTail(9);
        deleteSingleLinkedList.insertWithIndex(1, 6);
        deleteSingleLinkedList.print();
        deleteSingleLinkedList.deleteTail();
        deleteSingleLinkedList.print();
        deleteSingleLinkedList.insertHead(7);
        deleteSingleLinkedList.insertTail(1);
        deleteSingleLinkedList.print();
        deleteSingleLinkedList.deleteHead();
        deleteSingleLinkedList.print();
    }
}

执行结果：

打印链表节点数据：
4=>6=>9打印链表节点结束。
打印链表节点数据：
4=>6打印链表节点结束。
打印链表节点数据：
7=>4=>6=>1打印链表节点结束。
打印链表节点数据：
4=>6=>1打印链表节点结束。

说明：

‌头节点删除‌：直接将head指向head.next，Java的垃圾回收会自动处理原头节点的内存。

尾节点删除‌：遍历到倒数第二个节点，修改其next指针为null。对于单节点链表，直接置空head。

边界条件‌：处理空链表和单节点链表的情况，避免空指针异常。

‌时间复杂度：删除头部节点，直接修改头指针指向第二个节点即可，无需遍历链表，时间复杂度为O(1)‌；删除尾部节点，需要从头节点开始遍历链表，找到倒数第二个节点（前驱结点），然后将其 next 指针置为 null，时间复杂度为O(n)。

‌空间复杂度：删除头部节点，仅需修改指针，不依赖链表长度，无额外内存分配，空间复杂度为O(1)‌；删除尾部节点，仅需一个临时指针变量（如prev，即尾部节点的前驱节点），不依赖链表长度，时间复杂度为O(1)‌。

新增java单链表按照指定索引删除节点的方法：

public void deleteAtIndex(int index) {
    if(index < 0) throw new IllegalArgumentException("index error");
    if(head == null) return;

    ListNode prev = null;
    ListNode cur = head;
    int i = 0;
    // 找到对应索引的前驱节点，若index超过了链表长度，
    // 那么cur就是null，prev是尾结点；
    for(; cur != null && i < index; i++) {
        prev = cur;
        cur = cur.next;
    }
    if(prev == null) {
        deleteHead();
        return;
    }
    if(cur == null) {
        deleteTail();
        return;
    }
    prev.next = cur.next;
}

验证代码逻辑：

DeleteSingleLinkedList deleteSingleLinkedList = new DeleteSingleLinkedList();
deleteSingleLinkedList.insertHead(4);
deleteSingleLinkedList.insertTail(9);
deleteSingleLinkedList.insertWithIndex(1, 6);
deleteSingleLinkedList.print();
System.out.println("删除尾部节点：");
deleteSingleLinkedList.deleteTail();
deleteSingleLinkedList.print();
deleteSingleLinkedList.insertHead(7);
deleteSingleLinkedList.insertTail(1);
deleteSingleLinkedList.print();
System.out.println("删除头部节点：");
deleteSingleLinkedList.deleteHead();
deleteSingleLinkedList.print();
System.out.println("删除指定索引节点：");
deleteSingleLinkedList.deleteAtIndex(1);
deleteSingleLinkedList.print();
deleteSingleLinkedList.deleteAtIndex(0);
deleteSingleLinkedList.print();
deleteSingleLinkedList.deleteAtIndex(0);
deleteSingleLinkedList.print();

执行结果如下：

打印链表节点数据：
4=>6=>9打印链表节点结束。
删除尾部节点：
打印链表节点数据：
4=>6打印链表节点结束。
打印链表节点数据：
7=>4=>6=>1打印链表节点结束。
删除头部节点：
打印链表节点数据：
4=>6=>1打印链表节点结束。
删除指定索引节点：
打印链表节点数据：
4=>1打印链表节点结束。
打印链表节点数据：
1打印链表节点结束。
打印链表节点数据：

上述可知，删除链表节点的思路，无非找到待删除节点的前驱节点，将前驱节点的next指向待删除节点的next即可。

这里根据单链表节点删除的逻辑，举个栗子，见leetcode83. 删除排序链表中的重复元素：

给定一个已排序的链表的头head ， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表 。

解法如下：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            prev = cur;
            cur = cur.next;
            if (cur != null) {
                if (prev.val == cur.val) {
                    prev.next = cur.next;
                    cur = prev;
                }
            }
        }
        return head;
    }
}

上述解法就是根据单链表删除的基础操作思考得来：首先找到删除节点的前驱节点，这里因为单链表数据的特殊性，是升序排序，且去掉其重复的值，那么需要删除的重复节点，其前驱节点就是和相邻后续节点刚好值相等的情况，再进行删除相邻后节点的操作即可，注意这里因为重复值可能是连续多个以上（>=3），所以需要将prev即前驱节点重新指向cur节点，再与后续相邻节点再次进行判断即可。

但是注意，并不是一些需要断开指针连接的方式都会用到上述的删除操作，比如leetcode上经典的反转链表题目，如下：

leetcode 206. 反转链表:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode prev = null;
        ListNode cur = head;

        ListNode combine = null;
        while(cur != null) {
            combine = cur.next;
            cur.next = prev;
            prev = cur;
            cur = combine;
        }
        return prev;
    }
}

实际上解法是巧妙的指针指向的变化来实现链表反转的。

2.3.1 实现单链表节点移动

有了上述单链表节点的插入、删除的了解，下述的链表节点移动，实际上就是链表节点删除和链表节点插入操作的一个整合操作。

单链表节点移动操作步骤

• ‌确定移动目标‌：

将节点X移动到节点Y之后。

• ‌查找节点及前驱‌：

找到X的前驱节点prevX，找到目标节点Y。

• ‌解除原链接‌（也就是上述的删除节点）：

将X从原位置移除，调整prevX的next指针。

• ‌插入新位置‌（也就是上述的插入节点）：

将X插入到Y之后，调整Y的next指针。

边界条件处理

X是头节点：prevX为null，需更新头指针。
Y是尾节点：X成为新的尾节点。
X和Y相邻或相同：无需操作或特殊处理。
X或Y不存在于链表中：提前返回或报错。

下面的示例，以分别移动单链表节点到头部和尾部来进行说明：

public class MoveSingleLinkedList extends NewSingleLinkedList {

    public void moveToHead(ListNode target) {
        // 特殊说明： head == target说明目标节点已在头部，所以不做处理
        if(target == null || head == null || head == target) {
            return;
        }

        ListNode prevNode = getPrevNode(target);
        // 如果前驱节点为null，则不处理节点移动
        if(prevNode == null) return;
        // 首先根据找到的前驱节点，删除目标节点
        prevNode.next = target.next;
        // 再将目标节点，插入到头部
        target.next = head;
        // 最后将head头结点，重新指向当前最新的头结点
        head = target;
    }

    public void moveToTail(ListNode target) {
        // 特殊说明： head.next == null说明单链表只有1个节点，所以不做移动尾部处理
        // target.next: 说明目标节点已经是最尾部的节点了，所以不做移动尾部处理
        if(target == null || head == null ||
                head.next == null || target.next == null) {
            return;
        }

        ListNode prevNode = getPrevNode(target);
        // 注意：移动到尾部和头部有区别，如果前驱节点为null，头部则不处理节点移动
        // 因为移动到头部，前驱结点为null，可能目标节点已经是头部节点，或者是目标节点在单链表中不存在
        // 但是移动到尾部的时候，前驱节点如果为null，说明：目标节点已经是头部节点，
        // 当然也可能是目标节点不存在导致的，所以不能直接return
//        if(prevNode == null) return;

        if(prevNode == null) {
            // 可能是目标节点的前驱节点不存在，即目标节点是最头部节点；或者目标节点不存在于单链表
            // 所以下面仅判断  目标节点是最头部节点的情况，这里排除目标节点不存在于单链表中的情况
            if(target != head) {
                return;
            }
            // 如果目标节点就是头节点，需要移动到尾部，那么先删除头节点
            head = head.next;
            // 找到当前单链表的尾部节点
            ListNode cur = head;
            while(cur.next != null) {
                cur = cur.next;
            }
            // 插入目标节点：注意！！！目标节点的next指针需要清除，否则就是一个循环引用了
            // 和上面的移动头节点，思路保持一致：（1）先修改前驱节点的next指针
            // （2）再修改目标节点的next指针  （3）若有必要，修改head头指针指向
            cur.next = target;
            target.next = null;
            return;
        }
        // target.next为null，说明此时target已经是尾部节点，直接返回
        // 前面已经判断过  target.next == null的情况，所以这里不用额外判断了
//        if(target.next == null) {
//            return;
//        };
        // 首先根据找到的前驱节点，删除目标节点
        // 注意这里的target可能是尾部节点，也可能是除了头部节点外的其他节点
        prevNode.next = target.next;
        // 找到单链表的尾部节点
        ListNode cur = prevNode.next;
        while(cur.next != null) {
            cur = cur.next;
        }
        // 再将目标节点，插入到尾部
        // 思路：（1）先修改前驱节点的next指针
        // （2）再修改目标节点的next指针  （3）若有必要，修改head头指针指向
        cur.next = target;
        target.next = null;
    }

    /**
     * @param target 单链表的目标节点
     * @return 目标节点的前驱节点，也就是链表节点查询
     */
    public ListNode getPrevNode(ListNode target) {
        if(target == null || target == head) {
            return null;
        }
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null && cur != target) {
            prev = cur;
            cur = cur.next;
        }

        //  cur为null，说明target节点不存在于链表中，直接返回
        if(cur == null) {
            return null;
        }
        return prev;
    }


    public static void main(String[] args) {
        MoveSingleLinkedList moveSingleLinkedList = new MoveSingleLinkedList();
        moveSingleLinkedList.insertTail(9);
        moveSingleLinkedList.insertTail(1);
        moveSingleLinkedList.insertHead(8);
        moveSingleLinkedList.insertWithIndex(2,7);
        moveSingleLinkedList.insertWithIndex(1,6);
        moveSingleLinkedList.print();
        System.out.println("开始头部移动：");
        moveSingleLinkedList.moveToHead(moveSingleLinkedList.head.next.next);
        moveSingleLinkedList.print();
        moveSingleLinkedList.moveToHead(moveSingleLinkedList.head);
        moveSingleLinkedList.print();
        System.out.println("开始尾部移动：");
        moveSingleLinkedList.moveToTail(moveSingleLinkedList.head);
        moveSingleLinkedList.print();
        moveSingleLinkedList.moveToTail(moveSingleLinkedList.head.next);
        moveSingleLinkedList.print();
        System.out.println("开始头部移动：");
        moveSingleLinkedList.moveToHead(moveSingleLinkedList.head.next.next.next.next);
        moveSingleLinkedList.print();
        System.out.println("开始尾部移动：");
        moveSingleLinkedList.moveToTail(moveSingleLinkedList.head.next.next.next.next);
        moveSingleLinkedList.print();
    }

}

执行结果：

8=>6=>9=>7=>1打印链表节点结束。
开始头部移动：
打印链表节点数据：
9=>8=>6=>7=>1打印链表节点结束。
打印链表节点数据：
9=>8=>6=>7=>1打印链表节点结束。
开始尾部移动：
打印链表节点数据：
8=>6=>7=>1=>9打印链表节点结束。
打印链表节点数据：
8=>7=>1=>9=>6打印链表节点结束。
开始头部移动：
打印链表节点数据：
6=>8=>7=>1=>9打印链表节点结束。
开始尾部移动：
打印链表节点数据：
6=>8=>7=>1=>9打印链表节点结束。

说明：

‌移动到头部（Move to Head）‌

• ‌时间复杂度‌：‌O(n)‌

原因‌：

需要遍历链表找到目标节点的‌前驱节点‌（最坏情况下遍历整个链表）。
例如，若目标节点是最后一个节点，需要遍历全部 n 个节点。

• ‌空间复杂度‌：‌O(1)‌

原因‌：

仅使用常数级别的临时变量（如 prev），没有额外内存分配。

‌移动到尾部（Move to Tail）‌

• ‌时间复杂度‌：‌O(n)‌

原因‌：

若目标节点是头节点：需要遍历链表找到‌新的尾节点‌（遍历全部 n 个节点）。
若目标节点是中间节点：需要遍历找到目标节点的‌前驱节点‌（最坏 O(n)），再遍历找到‌原尾节点‌（最坏 O(n)）。

‌总计‌：两次遍历，但时间复杂度仍为 O(n)（系数可忽略）。

• ‌空间复杂度‌：‌O(1)‌

原因‌：

同样只使用常数级别的临时变量。

注意：如果频繁操作尾部，可以通过以下优化降低时间复杂度：

‌维护尾指针‌：

在链表中增加一个tail指针，指向尾节点。
‌移动到尾部的时间复杂度‌可降为 ‌O(1)‌（直接通过 tail 指针操作）。
但需要额外维护tail指针的更新逻辑（例如插入、删除节点时）。

2.4 总结

根据总结可知，时间复杂度为‌O(1)‌的情况有单链表节点的头部插入和头部节点删除，其余场景的时间复杂度为O(n)‌。