Middle of the Linked List-LeetCode#876

876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.
If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

链表的中间位置
给定具有头节点头的非空的单链表,返回链表的中间节点。如果有两个中间节点,则返回第二个中间节点。

思路:定义两个链表,为 temp 与 rate。temp 每次走一步,rate 每次走两步,当 rate 走完的时候,temp 刚好到中间位置。需要注意的是链表总数为偶数的情况下,需要返回 temp.next。
public ListNode middleNode(ListNode head) {
    ListNode temp = head;
    ListNode rate = head;
    while (rate != null && rate.next != null){
        if (rate.next != null && rate.next.next == null){
            return temp.next;
        }
        temp = temp.next;
        rate = rate.next.next;
    }
    return temp;
}
文章已创建 108

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部