Middle of Linked List
Description
Find the middle node of a linked list.
Example
Given 1->2->3
, return the node with value 2.
Given 1->2
, return the node with value 1.
Challenge
If the linked list is in a data stream, can you find the middle without iterating the linked list again?
/** * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { /** * @param head: the head of linked list. * @return: a middle node of the linked list */ public ListNode middleNode(ListNode head) { // write your code here if(head==null) return null; ListNode slow=head; ListNode fast=head; while(fast.next!=null&&fast.next.next!=null){ slow=slow.next; fast=fast.next.next; } return slow; }}
描述找链表的中点。您在真实的面试中是否遇到过这个题? 样例链表 1->2->3 的中点是 2。链表 1->2 的中点是 1。挑战如果链表是一个数据流,你可以不重新遍历链表的情况下得到中点么?