链表通过指针将一组零散的内存空间串联起来使用。
单链表
双向链表
循环链表
链表的特点
每一个内存块称之为节点
为了将所有节点联系起来 每个节点不仅要记录数据还要记录下一个内存块的地址
通常 第一个节点称之为头节点 最后一个节点称之为尾结点
链表的相关操作
data:节点元素
next:后继节点地址
下标访问:不支持
插入
q:插入的节点
p:当前节点
只需p->next = q就可以了 时间复杂度为O(1)
删除
k:删除节点
单纯的删除操作只需将k节点删除就可以了时间复杂度为O(1)
但删除元素后要将指向k的指针也删除 这就需要从头遍历了 时间复杂度为O(n)
这里有个小技巧 当k不为尾结点时
k->data = k->next->data;
k->next = k->next->next;
然后删除k->next 时间复杂度为 O(1)
查找
顺序遍历O(n)
将链表构建为跳表 查找的时间复杂度为O(n)
LeetCode234 回文链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null) {
if (fast.next == null) {
slow = slow.next;
break;
}
slow = slow.next;
fast = fast.next.next;
}
slow = reverse(slow);
fast = head;
while (slow != null) {
if (slow.val != fast.val) {
return false;
}
slow = slow.next;
fast = fast.next;
}
return true;
}
private ListNode reverse(ListNode head) {
if (head == null)
return null;
ListNode previous = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = previous;
previous = head;
head = next;
}
return previous;
}
}