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