---
title: "【面试算法笔记】0202-链表-基本功能实现"
source: https://www.zbhgis.com/note/note-20260504-1
author: zbhgis 浩瀚地学
created: 2026-05-04
tags: [面试算法笔记, 算法, LeetCode]
---

> 本文来自浩瀚地学，规范页面（含代码高亮与图片灯箱）：https://www.zbhgis.com/note/note-20260504-1
# 【面试算法笔记】0202-链表-基本功能实现

个人主页：https://github.com/zbhgis

# 前言

本系列主要记录自己学习算法的过程中的感悟。

# 力扣203. 移除链表元素

链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

## 注意点

链表操作的题目，为了减少判断操作，都可以引入一个虚拟头节点，指向head。

这里的移除操作，就是相当于将cur指向cur.next.next，跳过中间的cur.next，就是上一篇的图示。

本质就是遍历各个节点，然后修改指针指向，以及题目如果需要返回链表的话，就是返回头节点。

## 代码

```Java
/**
 * 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 removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}
```

## 时空复杂度分析

单层循环，最多需要遍历n次，n为链表长度，因此时间复杂度为O(n)

空间复杂度为O(1)

# 力扣707. 设计链表-单向

链接：https://leetcode.cn/problems/design-linked-list/description/

## 注意点

定义链表就不多说了。以及各个方法中的边界判断也就不说了，特殊的就是在addAtIndex中是可以到size下标。

get方法，就是设置一个cur，去遍历各个节点，到所需下标处返回。

addAtIndex方法，就是通过一个前驱节点，得到想要添加处的前一个节点prev，最后新的节点指向prev.next，prev指向新的节点。

deleteAtIndex方法，也是通过前驱节点遍历，只不过最后是把prev指向prev.next.next，跳过了所需下标的节点。

## 代码

```Java
public class MyLinkedList {

    // 单链表节点定义
    private class Node {
        int val;
        Node next;

        Node() {}
        Node(int val) { this.val = val; }
        Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    private Node dummy;   // 虚拟头节点
    private int size;     // 链表长度

    /** 初始化 */
    public MyLinkedList() {
        dummy = new Node(0);
        size = 0;
    }

    /** 获取下标 index 的节点值 */
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }

        Node cur = dummy.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    /** 头插法 */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    /** 尾插法 */
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    /** 在下标 index 前插入节点 */
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;

        Node prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        Node newNode = new Node(val);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }

    /** 删除下标 index 的节点 */
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;

        Node prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        prev.next = prev.next.next;
        size--;
    }
}
```

## 时空复杂度分析

除了addAtHead和addAtTail方法是O(1)，其他时间复杂度为O(n)

局部空间复杂度为O(1)，整体因为要存储n个节点，所以整体空间复杂度为O(n)

# 力扣707. 设计链表-双向

链接：https://leetcode.cn/problems/design-linked-list/description/

## 注意点

同上。

## 代码

```Java
class MyLinkedList {
    public class Node {
        int val;
        Node prev;
        Node next;

        Node() {}
        Node(int val) {this.val = val;}
        Node(int val, Node prev, Node next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
    private final Node dummyHead;
    private final Node dummyTail;
    private int size;
    public MyLinkedList() {
        dummyHead = new Node(0);
        dummyTail = new Node(0);

        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
        size = 0;
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node cur;
        if (index < size / 2) {
            cur = dummyHead.next;
            for (int i = 0; i < index; i ++) cur = cur.next;
        } else {
            cur = dummyTail.prev;
            for (int i = size - 1; i > index; i --) cur = cur.prev;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        Node prev, next;
        if (index < size / 2) {
            prev = dummyHead;
            for (int i = 0; i < index; i ++) prev = prev.next;
            next = prev.next;
        } else {
            next = dummyTail;
            for (int i = size; i > index; i --) next = next.prev;
            prev = next.prev;
        }
        
        Node newNode = new Node(val, prev, next);
        prev.next = newNode;
        next.prev = newNode;
        size ++;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node prev, next;
        if (index < size / 2) {
            prev = dummyHead;
            for (int i = 0; i < index; i ++) prev = prev.next;
            next = prev.next;
        } else {
            next = dummyTail;
            for (int i = size; i > index; i --) next = next.prev;
            prev = next.prev;
        }

        prev.next = next.next;
        next.next.prev = prev;
        size --;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
```

## 时空复杂度分析

同上

# 力扣206. 反转链表

链接：https://leetcode.cn/problems/reverse-linked-list/description/

## 注意点

从前往后遍历节点，但是需要遍历到的节点找到指针方向。

## 代码

```Java
/**
 * 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) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}
```

## 时空复杂度分析

单层循环，最多需要遍历n次，n为链表长度，因此时间复杂度为O(n)

空间复杂度为O(1)

# 参考

https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html