数据结构与算法之链表

　　链表这种数据结构，真的比较难以掌握的，感觉有点头疼。。。和数组相比，链表更适合插入。删除操作频繁的场景，查询的时间复杂度较高

一、链表种类

单链表、循环链表、双向链表

二、链表中常用的算法练习

/**
 * 节点的实体类
 * 
 * @author ssc
 * @date 2019.03.05
 */
public class Node {

    public int value;
    public Node next;
    
    public Node(){
        super();
    }
    
    public Node(int data) {
        this.value = data;
    }
}

/***
 * 链表结构中常用的
 * 
 * @author ssc
 * @date 2019.03.05
 */
public class Reverse {

    /**
     * 遍历法链表反转
     * 
     * @return
     */
    public static Node reverse1(Node list) {
        Node headNode = null;
        Node previousNode = null;
        Node currentNode = list;

        while (currentNode != null) {
            Node nextNode = currentNode.next;
            if (nextNode == null) {
                headNode = currentNode;
            }
            currentNode.next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
        return headNode;
    }

    /**
     * 链表中环的检测
     * 
     * @return
     */
    public static boolean checkCircle(Node list) {
        if (list == null) {
            return false;
        }
        Node fast = list.next;
        Node slow = list;

        if (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 两个有序链表合并
     * 
     * @param la
     *            有序链表a
     * @param lb
     *            有序链表b
     * @return
     */
    public static Node mergeSortedLists(Node la, Node lb) {

        if (la == null) {
            return lb;
        }
        if (lb == null) {
            return la;
        }
        Node p = la;
        Node q = lb;
        Node head;
        if (p.value < q.value) {
            head = p;
            p = p.next;
        } else {
            head = q;
            q = q.next;
        }
        Node r = head;

        while (p != null && q != null) {
            if (p.value < q.value) {
                r.next = p;
                p.next = p;
            } else {
                r.next = q;
                q.next = q;
            }
            r = r.next;
        }

        if (p != null) {
            r.next = p;
        } else {
            r.next = q;
        }
        return head;
    }

    /**
     * 删除倒数第k个结点
     * 
     * @param list 链表
     * @param k
     * @return
     */
    public static Node deleteLastKth(Node list, int k) {

        Node fast = list;
        
        int i = 1; // k=2
        while (fast != null && i < k) {
            fast = fast.next; // 2,3
            ++i;
        }
        
        if(fast == null){
            return list;
        }
        Node slow = list; // 1,2,3
        Node prev = null;
        
        while(fast.next != null){
            fast = fast.next; // 3
            prev = slow; // 1,2,3
            slow = slow.next; // 2,3
        }
        if(prev == null){
            list = list.next; 
        }else{
            prev.next = prev.next.next;
            printAll(prev);
        }
        return list;
    }
    
    /**
     * 求中间结点
     * 
     * @param list
     * @return
     */
    public static Node findMiddleNode(Node list){
        if(list == null){
            return null;
        }
        
        Node fast = list;
        Node slow = list;
        
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 打印链表中存储的数值
     * 
     * @param list
     */
    public static void printAll(Node list) {
        while (list != null) {
            System.out.print(list.value + " ");
            list = list.next;
        }
        System.out.println();
    }
}