链表

链表通过指针将一组零散的内存空间串联起来使用。
单链表

链表.jpg

双向链表.jpg

循环链表.jpg

链表的特点

每一个内存块称之为节点
为了将所有节点联系起来 每个节点不仅要记录数据还要记录下一个内存块的地址
通常 第一个节点称之为头节点 最后一个节点称之为尾结点

链表的相关操作

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;
    }
}