[LeetCode] 876. 链表的中间结点-三种方法实现

问题描述：

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点

示例1：

输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例2：

输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

第一种方法：先求链表的长度，然后求出中间位置，再遍历求中间节点

public ListNode middleNode(ListNode head) {         int length = listLength(head);         int position = length / 2 ;         System.out.println(position);         ListNode l = head;         for ( int i = 0 ; i < position ; i ++ ) {             l = l.next;         }         return l;              }       private int listLength(ListNode head) {         ListNode l = head;         int length = 0;         while( l != null ) {             length ++;             l = l.next;         }         return length;     }

第二种方法：以每个节点为头节点，将每个节点保存到数组中，返回数组中间的节点

public ListNode middleNode(ListNode head) {         ListNode [] array = new ListNode[100];         int i = 0 ;         while (head != null) {             array[i] = head ;             i ++ ;             head = head.next;         }         return array[i / 2];     }

第三种方法：快慢指针

 1.慢指针一次走一步，快指针一次走2步，快指针走到末端，慢指针正好指向中间结点； 2.这里分两种情况：

快指针的next为null，慢指针正好指向中间结点，链表结点数为偶数；快指针为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;     }