【数据结构与算法 | 链表篇】力扣876

1. 力扣876 : 链表的中间节点

(1). 题

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

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

示例 1：

 

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

 

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

(2). 思路 : 辅助数组

我发现链表的很多题目，尤其是简单题，大部分都可以用辅助数组来解决，让链表问题直接转化为数组问题. 

(3). 解

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {if (head == null) {return head;}ListNode p = head;int count = 0;while (p != null) {count++;p = p.next;}int[] arr = new int[count];p = head;for (int i = 0; i < count; i++) {arr[i] = p.val;p = p.next;}p = head;for (int i = 0; i < count/2; i++) {p = p.next;}return p;}
}

(4). 思路2 : 快慢指针

依据快慢指针，快指针一次走两步，慢指针一次走一步.

(5). 解2

class Solution {public ListNode middleNode(ListNode head) {if(head == null) {return null;}ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}return fast.next == null ? slow : slow.next;}
}