链表汇总

知识点

java中链表节点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ListNode{
    // 用途：用于存放节点所包含的值，这里用int举例
    int value;
    // 用途：用于存放下一个节点的地址
    // 类比：和开发中一个类中包含另一个类类似，只不过包含的类型和本类型一致
    ListNode next;

    // 构造器
    // 1.无参构造
    public ListNode() {}

    // 2.有参构造
    public ListNode(int value) {
        this.value = value;
    }

    // 3.全参构造
    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }
}

链表删除

cur ：为当前某个链表的节点

cur.value：取出当前节点值域存放的具体值 类比到：xxx.value

cur.next：

  • 当前链表的指针域，用来存放下一个节点的地址
  • 也可以代表cur的下一个节点，因为按照地址取值

cur.next.next：cur下一个节点的下一个节点的地址

1
cur.next = cur.next.next;

题目

T203 移除链表元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 判断头节点为符合条件的情况
        while (head != null && head.val == val) {
            head = head.next; // 将存放头节点的变量变为下一个
        }
        ListNode cur = head; // 头节点固定存放第一个元素,创建一个cur指针来遍历删除需要的节点
        while (cur != null) { // 如果
            while (cur.next != null && cur.next.val == val) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        return head;
    }
}
  • 为什么链表题目都只是传入一个头节点head/返回一个头节点？
    • 核心是指针域。因为链表节点这种数据结构，通过一个每个节点的指针域就可以得到下一个节点，以此类推，知道最后一个节点的指针域为null。
  • 为什么需要判断cur != null ?
    • 避免cur为null时，调用cur.value导致空指针异常，即null取属性/null调用方法
  • 为什么一般都是重新定义一个ListNode cur = head？
    • 因为一般head是固定的，需要用一个头节点去代表返回处理后的链表
    • 用一个cur节点去代替head遍历，从而进行链表的操作/改变链表元素
    • 15900000024 whjf@2023

T