链表常见面试题

单链表的创建和遍历

/**
 * 单链表的创建和遍历
 * 
 * @author adminjack
 *
 */
public class LinkList {
    public Node head;
    public Node current;

    // 方法：向链表中添加数据
    public void add(int data) {
        // 判断链表为空的时候
        if (head == null) {// 如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
            head = new Node(data);
            current = head;
        } else {
            // 创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
            current.next = new Node(data);
            // 把链表的当前索引向后移动一位
            current = current.next; // 此步操作完成之后，current结点指向新添加的那个结点
        }
    }

    // 方法：遍历链表（打印输出链表。方法的参数表示从节点node开始进行遍历
    public void print(Node node) {
        if (node == null) {
            return;
        }

        current = node;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    class Node {
        // 注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
        int data; // 数据域
        Node next;// 指针域

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

    public static void main(String[] args) {
        LinkList list = new LinkList();
        // 向LinkList中添加数据
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        list.print(list.head);// 从head节点开始遍历输出
    }
}

求单链表中节点的个数

注意检查链表是否为空。时间复杂度为O（n）。

//方法：获取单链表的长度
    public int getLength(Node head) {
        if (head == null) {
            return 0;
        }

        int length = 0;
        Node current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        return length;
    }

https://www.cnblogs.com/smyhvae/p/4782595.html

关于链表反转的
https://blog.csdn.net/xu491361421xiao/article/details/81385435

/**
     * 递归方式
     * 
     * @param node
     * @return
     */
    public Node reverseList2(Node head) {
        if (head.next == null) {
            return head;
        }

        Node prevNode = reverseList2(head.next);

        prevNode.next = head;

        head.next = null;

        return prevNode;
    }

    /**
     * 这个最好理解
     * 
     * @param H
     * @return
     */
    public Node reverseList3(Node H) {
        if (H == null || H.next == null) // 链表为空或者仅1个数直接返回
            return H;
        Node p = H, newH = null;
        while (p != null) // 一直迭代到链尾
        {
            Node tmp = p.next; // 暂存p下一个地址，防止变化指针指向后找不到后续的数
            p.next = newH; // p.next指向前一个空间
            newH = p; // 新链表的头移动到p，扩长一步链表
            p = tmp; // p指向原始链表p指向的下一个空间
        }
        return newH;
    }

    class Node {
        // 注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
        int data; // 数据域
        Node next;// 指针域

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

        @Override
        public String toString() {
            return String.valueOf(data);
        }
    }