- 链表中表示一个节点的类
private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
element表示节点的值,next表示当前节点的下一个节点
- 全局变量
private int size;
private Node<E> first;
size表示链表的长度,first表示链表的头节点
- 获取索引节点
private Node<E> node(int index) {
checkRange(index);
Node node = first;
for (int i = 0; i < index; i++) {
node = first.next;
}
return node;
}
从头节点遍历获取到index节点,返回index节点的node
- 修改index节点的值
public E set(int index, E element) {
Node<E> node = node(index);
E oldValue = node.element;
node.element = element;
return oldValue;
}
先获取index节点的node,然后修改node.element
- 添加节点
public void add(int index, E element) {
checkRangeForAdd(index);
if (index == 0) {
first = new Node<E>(element, first);
} else {
Node<E> prev = node(index - 1);
prev.next = new Node<E>(element, prev.next);
}
size++;
}
index=0表示添加头节点,直接初始化first
在指定index位置添加节点,就是在index-1和index+1中间位置添加element,index-1.next=index.next=index+1.next
- 删除索引位置节点
public E remove(int index) {
Node<E> node = first;
if (index == 0) {
first = first.next;
} else {
Node prev = node(index - 1);
node = prev.next;
prev.next = node.next;// prev.next = prev.next.next;
}
return node.element;
}
index=0表示删除头节点,让first.next等于first
index非0,先获取index-1节点的位置(index的前驱),让(index-1).next=index.next
前驱节点.next=后继节点,代码node = prev.next
node就是index节点
- 获取index位置元素
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element.equals(null)) return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return -1;
}
从first节点开始便利到size,进行equals()判断
- index校验
private void checkRangeForAdd(int index) {
if (index < 0 || index > index) {
indexOutOfBoundException(index);
}
}
private void checkRange(int index) {
if (index < 0 || index >= index) {
indexOutOfBoundException(index);
}
}
- 遍历链表
Node node = first;
for (int i = 0; i < size; i++) {
node = node.next;
}
从first开始for编列到size
Node node = first;
while (node != null) {
node = node.next;
}
从first开始遍历,只有first.next!=null就一直while()
- 反转链表
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = null;
while (head != null) {
ListNode tmp = head.next;
head.next = newHead;
newHead = head;
head = tmp;
}
return newHead;
}
- 判断是否环形链表
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
- 删除链表中的节点
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
网友评论