876. Middle of the Linked List 「链表的中间结点」

2020年04月04日 116点热度 1人点赞 0条评论

给定一个非空单链表,返回中间节点。

如果中间有两个节点,返回第二个。

例一:
输入: [1,2,3,4,5]
输出: 值为 3 的节点

例二:
输入: [1,2,3,4,5,6]
输出: 值为 4 的节点

提示:
链表的长度在 1 到 100 之间。

常用方法,快慢法,使用速度为 1 和 2 的两个节点来遍历链表,当快节点跑完了整个链表,慢节点就是中间节点。

/*
 * 876. Middle of the Linked List
 * https://leetcode.com/problems/middle-of-the-linked-list/
 * https://realneo.me/876-middle-of-the-linked-list/
 */

public class MiddleNode {
    public static void main(String[] args) {
        MiddleNode solution = new MiddleNode();

        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 7; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }

        solution.print(head);
        node = solution.middleNode(head);
        solution.print(node);
    }

    private void print(ListNode node) {
        for (; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

Neo

与卿再世相逢日,玉树临风一少年。

文章评论