leetcode 876, middle node of linked list (fast and slow pointer method)

Given a non empty single linked list with head node, the middle node of the linked list is returned.

If there are two intermediate nodes, the second intermediate node is returned.

Example 1:

Input: [1,2,3,4,5]
Output: node 3 in this list (serialization form: [3,4,5])
The returned node value is 3. (the serialization expression of the evaluation system for this node is [3,4,5]).
Note that we return an object ans of type ListNode, as follows:
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 in this list (serialization form: [4,5,6])
Since the list has two intermediate nodes with values of 3 and 4, we return the second node.

Tips:

The number of nodes in a given list is between 1 and 100.

My simple idea: traverse twice

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        int total = 0;
        ListNode cur = head;
        while (cur != null) {
            total++;
            cur = cur.next;
        }
        cur = head;
        for(int i = 0; i < total / 2; i++) {
            cur = cur.next;
        }
        return cur;
    }
}

Other ideas:

I. output to array and solve the problem with index

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode[] cur = new ListNode[100];
        int total = 0;
        while (head != null) {
            cur[total++] = head;
            head = head.next;
        }
        return cur[total / 2];
    }
}

II. Fast and slow pointer method

When traversing a list with a slow pointer, it's twice as fast to let the other pointer fast. When fast reaches the end of the list, slow must be in the middle.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    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;
    }
}

Posted on Fri, 29 Nov 2019 23:29:21 -0800 by emceej