Java数据结构之单链表的实现与面试题汇总

一、前言

单链表是数据结构中最基础的数据结构之一，也是在面试时经常会考察的一个知识点。本文将详细介绍单链表的实现过程，并对常见的单链表面试题进行总结，帮助大家深入了解单链表的原理和应用。

二、单链表的实现

单链表是由一些列节点构成的，每个节点包括一个数据和一个指向下一个节点的指针。下面我们将实现一个简单的单链表，并提供对应的操作方法，包括：

1. 添加节点；
2. 删除节点；
3. 插入节点；
4. 遍历节点；
5. 查找节点。

1. 定义节点类

节点类的作用是定义节点的数据和指向下一个节点的指针，我们来看实现：

public class ListNode {
    // 存放数据
    int val;
    // 指向下一个节点的指针
    ListNode next;

    // 构造函数
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

2. 定义单链表类

在单链表类中，我们需要将每个节点连接起来，并提供对应的操作方法：

public class LinkedList {
    // 头节点
    ListNode head;

    // 构造函数
    public LinkedList() {
        this.head = null;
    }

    // 添加节点
    public void addNode(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else {
            ListNode curr = head;
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = newNode;
        }
    }

    // 删除节点
    public void deleteNode(int val) {
        if (head == null) {
            return;
        }
        if (head.val == val) {
            head = head.next;
        } else {
            ListNode prev = head;
            ListNode curr = head.next;
            while (curr != null && curr.val != val) {
                prev = curr;
                curr = curr.next;
            }
            if (curr != null && curr.val == val) {
                prev.next = curr.next;
            }
        }
    }

    // 插入节点
    public void insertNode(int val, int index) {
        if (index < 0) {
            return;
        }
        if (index == 0 || head == null) {
            addNode(val);
        } else {
            ListNode newNode = new ListNode(val);
            int count = 0;
            ListNode curr = head;
            ListNode prev = null;
            while (curr != null && count < index) {
                prev = curr;
                curr = curr.next;
                count++;
            }
            prev.next = newNode;
            newNode.next = curr;
        }
    }

    // 遍历节点
    public void traverseNode() {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    // 查找节点
    public ListNode searchNode(int val) {
        ListNode curr = head;
        while (curr != null && curr.val != val) {
            curr = curr.next;
        }
        return curr;
    }
}

3. 单链表使用样例

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // 添加节点
        list.addNode(1);
        list.addNode(2);
        list.addNode(3);
        list.addNode(4);

        // 删除节点
        list.deleteNode(4);

        // 插入节点
        list.insertNode(5, 2);

        // 遍历节点
        list.traverseNode();

        // 查找节点
        System.out.println(list.searchNode(5).val);
    }
}

三、面试题汇总

1. 链表反转

题目描述：将一个链表进行反转，例如输入[1, 2, 3, 4]反转后输出为[4, 3, 2, 1]。

解题思路：使用三个指针逐个反转链表。具体看代码：

public ListNode reverseList(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode prev = null;
    ListNode curr = head;
    ListNode next = null;
    while (curr != null) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

2. 链表中环的检测

题目描述：给定一个链表，判断链表中是否存在环。

解题思路：如果链表中存在环，那么两个指针迭代时将一直重合。

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

四、总结

本篇文章对Java数据结构之单链表的实现进行了详细的介绍，并提供对应的操作方法。同时，针对常见的单链表面试题也进行了总结，希望能对大家在学习和面试中有所帮助。