打印链表的中间节点java

在Java中，打印链表的中间节点通常需要遍历整个链表两次，一次快慢指针法。这种方法可以有效地解决在不知道链表长度的情况下寻找中间节点的问题。以下是基本步骤：

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

public class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 使用快慢指针，快指针每次移动两步，慢指针每次移动一步
        ListNode slow = head, fast = head.next;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 当快指针到达链表末尾时，慢指针正好指向链表的中间节点
        return slow;
    }
}

当你运行这个函数，传入链表头节点后，它会返回链表的中间节点。如果没有中间节点（即链表只有一个元素），则直接返回头节点。

相关问题

什么是链表，语言是java,案例要详细，注释详细，新手看的懂

链表是一种常见的数据结构，它由若干个节点组成，每个节点包含一个元素以及指向下一个节点的指针。链表中的节点在内存中可以不连续，它们通过指针串联在一起。相比于数组等数据结构，链表可以动态地插入、删除元素，但是访问元素需要遍历整个链表。链表常见的操作包括插入元素、删除元素、查找元素等。

下面以Java语言为例，介绍链表的实现。

首先，我们定义链表节点的类Node：

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

其中，val表示节点存储的元素，next表示指向下一个节点的指针。接下来，我们定义链表类LinkedList：

public class LinkedList {
    private Node head;
    private int size;
    public LinkedList() {
        head = null;
        size = 0;
    }
    public int getSize() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    // 在链表头添加元素
    public void addFirst(int val) {
        Node node = new Node(val);
        node.next = head;
        head = node;
        size++;
    }
    // 在链表尾添加元素
    public void addLast(int val) {
        if (head == null) {
            addFirst(val);
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new Node(val);
            size++;
        }
    }
    // 在链表中间添加元素
    public void add(int index, int val) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index out of range.");
        }
        if (index == 0) {
            addFirst(val);
        } else {
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            Node node = new Node(val);
            node.next = prev.next;
            prev.next = node;
            size++;
        }
    }
    // 删除链表头元素
    public void removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("Cannot remove from empty list.");
        }
        head = head.next;
        size--;
    }
    // 删除链表尾元素
    public void removeLast() {
        if (head == null) {
            throw new NoSuchElementException("Cannot remove from empty list.");
        }
        if (size == 1) {
            head = null;
        } else {
            Node cur = head;
            while (cur.next.next != null) {
                cur = cur.next;
            }
            cur.next = null;
        }
        size--;
    }
    // 删除链表中间元素
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index out of range.");
        }
        if (index == 0) {
            removeFirst();
        } else if (index == size - 1) {
            removeLast();
        } else {
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            prev.next = prev.next.next;
            size--;
        }
    }
    // 查找元素是否存在
    public boolean contains(int val) {
        Node cur = head;
        while (cur != null) {
            if (cur.val == val) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    // 获取链表某个位置的元素
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index out of range.");
        }
        Node cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }
    // 改变链表某个位置的元素
    public void set(int index, int val) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index out of range.");
        }
        Node cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.val = val;
    }
    // 打印链表
    public void printList() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

我们实现了以下方法：

- getSize()：获取链表元素个数。
- isEmpty()：判断链表是否为空。
- addFirst(int val)：在链表头添加元素。
- addLast(int val)：在链表尾添加元素。
- add(int index, int val)：在链表中间添加元素。
- removeFirst()：删除链表头元素。
- removeLast()：删除链表尾元素。
- remove(int index)：删除链表中间元素。
- contains(int val)：查找元素是否存在。
- get(int index)：获取链表某个位置的元素。
- set(int index, int val)：改变链表某个位置的元素。
- printList()：打印链表中所有元素。

下面是一些具体的使用示例：

LinkedList list = new LinkedList();
list.addFirst(1);
list.addFirst(2);
list.addLast(3);
list.add(2, 4);
list.printList(); // 2 1 4 3
list.remove(1);
list.printList(); // 2 4 3
list.set(1, 5);
list.printList(); // 2 5 3
System.out.println(list.contains(5)); // true
System.out.println(list.get(1)); // 5

以上就是链表的Java实现，通过这个例子可以更好地理解链表的概念和使用方法。