Java 详细分析四个经典链表面试题

简介

链表是数据结构中非常常见的一种形式，在Java中也有非常多的实现方式。本文将介绍Java中四个经典的链表面试题，并且详细分析它们的实现方法。在介绍每一个题目的详细实现之前，我们将简单介绍Java链表和链表常见操作。

Java链表

链表是一种线性结构，其中每个节点包含了一个数据域和一个指针域，指向下一个节点。Java中常用的链表包括单向链表、双向链表和循环链表。常见的链表操作包括增加节点、删除节点、遍历链表等。

以下是一个单向链表的Java实现示例：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

题目一：反转链表

给定一个链表，将其反转并返回新的链表头节点。

以下是Java中反转链表的实现示例：

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

题目二：合并两个有序链表

将两个有序链表合并成一个新的有序链表并返回新链表的头节点。

以下是Java中合并两个有序链表的实现示例：

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

题目三：查找链表的中间节点

给定一个链表，返回链表的中间节点。如果链表的长度是偶数，则返回中间节点的后一个节点。

以下是Java中查找链表中间节点的实现示例：

public class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

题目四：删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第N个节点并返回链表的头节点。

以下是Java中删除链表倒数第N个节点的实现示例：

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int length  = 0;
        ListNode first = head;
        while (first != null) {
            length++;
            first = first.next;
        }
        length -= n;
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummy.next;
    }
}

总结

本文详细讲解了Java中四个经典的链表面试题的实现方法，包括反转链表、合并两个有序链表、查找链表的中间节点和删除链表倒数第N个节点。通过对这些题目的实现分析，我们可以加深对链表的掌握和理解。