一.链表

1.单向链表基础

一种链式存取的数据结构，单链表中的数据是以结点的形式存在，每一个结点是由数据元素和下一个结点的存储的位置组成。单链表与数组相比的最大差别是：单链表的数据元素存放在内存空间的地址是不连续的，而数组的数据元素存放的地址在内存空间中是连续的，这也是为什么根据索引无法像数组那样直接就能查询到数据元素

2.单向链表基本操作

包括链表的增删查改，以及判别某结点是否存在链表中
（1）链表类结构

public class Linked <T>{
	
	private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
	}
	private Node head;    		//头结点
	private int size;		//链表元素个数
	//构造函数
	public Linked(){
		this.head = null;
		this.size = 0;
	}
}

（2）插入
头部插入：node.next = this.head 新节点的下个元素指向当前头节点
中间插入：node.next = preNode.next; preNode.next = node; 要插入的节点的下一个节点指向preNode节点的下一个节点 & preNode的下一个节点指向要插入节点node

        //链表头部添加元素
	public void addFirst(T t){
		Node node = new Node(t);	//节点对象
		node.next = this.head;
		this.head = node;
		this.size++;
		//this.head = new Node(e,head);等价上述代码
	}
	//向链表尾部插入元素
	public void addLast(T t){
		this.add(t, this.size);
	}
       //向链表中间插入元素
       public void add(T t,int index){
        if (index <0 || index >size){
            throw new IllegalArgumentException("index is error");
        }
        if (index == 0){
            this.addFirst(t);
        }
        Node preNode = this.head;
        //找到要插入节点的前一个节点
        for(int i = 0; i < index-1; i++){
            preNode = preNode.next;
        }
        Node node = new Node(t);
        //要插入的节点的下一个节点指向preNode节点的下一个节点
        node.next = preNode.next;
        //preNode的下一个节点指向要插入节点node
        preNode.next = node;
        this.size++;
    }

（2）删除
当cur.next 为要删除的节点时，cur.next = curr.next.next

        //删除链表元素
	public void remove(T t){
		if(head == null){
			System.out.println("无元素可删除");
			return;
		}
		//要删除的元素与头结点的元素相同
		while(head != null && head.t.equals(t)){
			head = head.next;
			this.size--;
		}
		/**
		 * 上面已经对头节点判别是否要进行删除
		 * 所以要对头结点的下一个结点进行判别
		 */
		Node cur = this.head;
		while(cur.next != null){
			if(cur.next.t.equals(t)){
				this.size--;
				cur.next = cur.next.next;
			}
			else cur = cur.next;
		}
		
	}

3.单链表的倒数第k个元素

快慢指针，从头遍历

public LinkList kNum(LinkList list, int k) {
        if (list == null || k < 1)
            return null;
        int num = 0;
        LinkList low = list;
        LinkList height = list;
        while (height != null) {
            if (num != k) {
                height = height.next;
                num++;
            }
            low = low.next;
            height = height.next;
        }
        if (num < k)
            return null;
        else
            return low;
    }

4.单链表反转

（1）遍历法：在链表遍历的过程中将指针顺序置换

 public static Node reverseNode(Node node){
        Node pre = null;
        Node next = null;
        while (node != null){
            //保存node的next节点
            next = node.next;
            //node的next节点指向前一个节点
            node.next = pre;
            //node的前一个节点变为node
            pre = node;
            //node变为下一个节点
            node = next;
        }
        return pre;
    }

（2）递归法：从最后一个Node开始，在弹栈的过程中将指针顺序置换的

public static Node reverse(Node node){
        if (node == null && node.next == null)return node;
        //保存node的next节点
        Node temp = node.next;
        //反转next链表
        Node newNode = reverse(node.next);
        //经过反转的链表next指向头
        temp.next = node;
        //头next指向null
        node.next = null;
        return newNode;
    }

5.双向链表的基本操作

单链表查找方向只能是一个方向，并且删除一个节点依赖于它的前一个节点
（1）插入
需要处理4个指向

            node.pre = pre;
            node.next = pre.next;
            pre.next.pre = node;
            pre.next = node;

（2）删除

cur.pre.next = cur.next;
if(cur.next!=null){
    ur.next.pre = cur.pre;
}

6.判断链表成环

首先创建两个指针p1和p2，让它们同时指向这个链表的头节点。然后遍历链表，p1每次移动一个节点，p2每次移动两个节点，然后比较指向的节点是否相同，相同则说明有环

public static boolean isCycle(Node head) {
        Node p1 = head;
        Node p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                return true;
            }
        }
        return false;
}

【总结】2.链表

原文：https://www.cnblogs.com/muacheng/p/13508958.html