单链表相关操作

在面试中，链表的操作一直是个很常见的考察点，之前也一直觉得链表相关操作很难，但是只要多动手练一练，没有那么难，最怕的就是只看不写，看完就溜。
链表中常见的操作主要有：

• 创建一个链表
• 向链表中添加节点
• 删除链表中的某个节点
• 链表翻转的两种方式(递归、非递归)
• 查找链表的中间节点或者倒数第k个节点
• 检测链表是否包有环

code

package com.program;
class LinkedList {
    private Node head;
    /**
     * 添加链表节点
     *
     * @param data
     */
    public void addNode(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(data);
    }

    /**
     * 删除链表节点
     *
     * @param index
     */
    public void deleteNode(int index) {
        if (index < 0 || index > getLength() - 1) {
            return;
        }
        Node temp = head;
        if (index == 0) {
            head = head.next;
            return;
        }
        int i = 0;
        while (temp != null && i != index - 1) {
            temp = temp.next;
            i++;
        }
        if (temp.next.next != null) {
            temp.next = temp.next.next;
        } else {
            temp.next = null;
        }
    }

    /**
     * 链表翻转：方法1，
     * 主要思路：
     * 把当前节点的下一个节点暂存，作为后面遍历的节点
     * 把当前节点暂存，作为下个节点的next节点，
     */
    public void reverseList() {
        if (head == null || head.next == null) {
            return;
        }
        Node temp = head;
        Node preNode = null;
        while (temp != null) {
            Node nextNode = temp.next;
            if (nextNode == null) {
                head = temp;
            }
            temp.next = preNode;
            preNode = temp;
            temp = nextNode;
        }
    }

    /**
     * 递归方式实现链表翻转，递归的确是难以理解啊。
     *
     * @param head
     * @return
     */
    public Node reverseList2(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node newNode = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return newNode;
    }

    /**
     * 查找当前单链表的中间节点，
     * 主要思路：
     * 两个指针，一个一次走两步，一个一次走一步，两步结束，一步到中间
     */
    public void searchMidNode() {
        Node temp1 = head;
        Node temp2 = head;
        while (temp2.next != null && temp2.next.next != null) {
            temp2 = temp2.next.next;
            temp1 = temp1.next;
        }
        System.out.println(temp1.node);
    }

    /**
     * 查找倒数第k个元素
     * 主要思路：
     * 两个指针，一个先走k步，然后另一个再走，第一个走到头了，over.
     *
     * @param k
     */
    public void findElem(int k) {
        if (k < 0 || k > getLength()) {
            return;
        }
        Node temp1 = head;
        Node temp2 = head;
        int i = 1;
        while (i < k) {
            temp1 = temp1.next;
            i++;
        }
        while (temp1.next != null) {
            temp1 = temp1.next;
            temp2 = temp2.next;
        }
        System.out.println(temp2.node);

    }

    /**
     * 判断链表是否有环
     * 主要思路，两个不同速度的指针同时出发，如果快指针追上慢指针，那么一定有环了。跑道就是这个道理。
     *
     * @return
     */
    public boolean isLoop() {
        Node fast = head;
        Node slow = head;
        if (head == null || head.next == null) {
            return false;
        }
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 获取链表长度
     *
     * @return
     */
    private int getLength() {
        Node tmp = head;
        int i = 0;
        while (tmp != null) {
            i++;
            tmp = tmp.next;
        }
        return i;
    }

    public static void printList(LinkedList linkedList) {
        Node head = linkedList.head;
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.node + " ");
            temp = temp.next;
        }
    }

    public Node getHead() {
        return head;
    }

    public static void main(String[] args) throws java.lang.Exception {
        System.out.println("zhou'xiang");
        LinkedList listss = new LinkedList();
        listss.addNode(5);
        listss.addNode(4);
        listss.addNode(2);
        listss.addNode(0);
        listss.addNode(1);
        System.out.println("原始链表如下");
        printList(listss);
        System.out.println("\n删除第0个节点之后的链表如下");
        listss.deleteNode(0);
        printList(listss);
        System.out.println("\n翻转之后如下");
        listss.reverseList();
        printList(listss);
        System.out.println("\n再次翻转之后如下");
        listss.reverseList();
        printList(listss);
        System.out.println("\n链表中间值为");
        listss.searchMidNode();
        System.out.println("链表倒数第2个节点为：");
        listss.findElem(2);
        System.out.println("\n递归翻转之后如下：");
        listss.reverseList2(listss.getHead());
        //printList(listss);
    }

    class Node {
        int node;
        Node next;
        public Node(int data) {
            this.node = data;
        }
    }
}