当前位置：首页 > news >正文

算法通关村第一关|青铜|链表笔记

news 2025/6/27 0:18:36

1.理解 Java 如何构造出链表

在 Java 中，我们创建一个链表类，类中应当有两个属性，一个是结点的值 val ，一个是该结点指向的下一个结点 next 。 next 通俗讲是一个链表中的指针，但是在链表类中是一个链表类型的引用变量，这点是之前我会忽视的。所以根据面向对象的理论，在 Java 里规范的链表应该定义为：

public class ListNode {private int data;private ListNode next;public ListNode(int data){this.data = data;}public int getData(){return data;}public void setData(int data){this.data = data;}public ListNode getNext(){return next;}public void setNext(ListNode next){this.next = next;}
}

但是在算法题中为了精简会使用其他方式创建链表：

public class ListNode{// 使用了公共权限，可以直接访问到val和next的值public int val;public ListNode next;ListNode(int x){val = x;next = null;}
}
ListNode listnode = new ListNode(1);

2.链表增加元素时会有什么问题，该如何处理

当链表为空即 head 为 null 的时候，要插入的结点就是链表的头结点。当然也可以抛出不能插入的异常。

3.双向链表如何构造

双向链表就是每一个链表对象内部多存储一个前趋指针，写一个算法题中的精简版本：

public class DoublyListNode{public int val;public DoublyListNode prev;public DoublyListNode next;DoublyListNode(int x){val = x;prev = null;next = null;}
}
DoublyListNode doublyListnode = new DoublyListNode(1);