单链表
单链表是一种线性表,与顺序表不同的是,链表在内存中的存放不是连续的。链表是由一个个节点构成,链表的第一个节点叫头结点,最后一个节点叫尾结点,每个节点里有节点的数据值和一个内存地址,内存地址指向下一个节点,其中尾结点指向null。链表相较顺序表有内存利用率高和元素插入、查找、删除效率高的优势。
链表
如上图所示,每个节点都有一个next地址,next地址指向下一个节点,
- 获取某个位置的节点对象
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
- 根据节点返回节点位置
public int indexOf(E element) {
if (element == null) { // 1
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == 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; // n
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
- 删除节点
public E remove(int index) {
//获取index位置的节点
Node<E> node = node(index);
if (index == 0) {
first = first.next;
}else {
Node<E> prevNode = node(index-1);
prevNode.next = prevNode.next.next;
}
size--;
return node.element;
}
- 添加节点
public void add(int index, E element) {
if (index == 0) {
first = new Node<>(element, first);
}else {
Node<E> prevNode = node(index-1);
Node<E> node = new Node<>(element, prevNode.next);
prevNode.next = node;
}
size++;
}
- 修改节点的值
public E set(int index, E element) {
Node<E> node = node(index);
E oldE = node.element;
node.element = element;
return oldE;
}
练习
链表翻转(leetcode地址),输入一个链表的头结点,翻转整个链表
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
递归法
链表翻转后原来的尾结点变为头结点,所以递归要返回原链表的尾结点,递归的出口为if(head == null || head.next == null) return head;
递归过程
代码:
public class _206_反转链表 {
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
迭代法
创建临时节点对象tmp,tmp指向当前节点head的next。创建newHead节点对象,newHead指向已经翻转好的链表的头,从头结点开始遍历链表,将tmp指向当前节点head的next,newHead再指向head,当前节点指向tmp,完成一次遍历。
迭代过程
代码:
public class _206_反转链表 {
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
while(head != null) {
ListNode tmp = head.next;
head.next = newHead;
newHead = head;
head = tmp;
}
return newHead;
}
}