给定一个头节点为 head 的非空单链表，返回链表的中间节点。
如果有两个中间节点，则返回第二个中间结点。

  1. 输入：[1,2,3,4,5]
  2. 输出：3
  4. 输入：[1,2,3,4,5,6]
  5. 输出：4
  7. 提示：
  8.     给定链表的结点数介于 1 和 100 之间

快慢指针

此题其实是为了找到中间结点，我个人使用 快慢指针 的思路来实现，两个指针同时从头结点出发，慢结点一次走一步，快结点一次走两步，当快结点到达链表尾部的时候慢结点正好到中间结点（ 奇数的时候 ），当偶数的时候中间结点再往后移一位即可。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     struct ListNode *next;
  6.  * };
  7.  */
  10. struct ListNode* middleNode(struct ListNode* head){
  11.     struct ListNode *slow = head;
  12.     struct ListNode *fast = head;
  13.     while (fast->next && fast->next->next) {
  14.         slow = slow->next;
  15.         fast = fast->next->next;
  16.     }
  17.     if (fast->next) {
  18.         slow = slow->next;
  19.     }
  20.     return slow;
  21. }
  • 时间复杂度： O(N)
  • 空间复杂度： O(1)

    数组

    链表的缺点是不能通过下表访问指定的元素。因此我们可以考虑对链表进行遍历，同时将遍历到的元素依次放入数组中，然后我们就知道数组的长度，很容易就取到中间的值。
    1. public ListNode middleNode(ListNode head) {
    2.       ListNode[] A = new ListNode[100];
    3.       int t = 0;
    4.       while (head != null) {
    5.           A[t++] = head;
    6.           head = head.next;
    7.       }
    8.       return A[t / 2];
    9.   }
    时间复杂度： O(N)
    空间复杂度： O(N)

单指针法

上面的方法无非是为了获取链表的长度，我们同样可以通过链表的遍历直接获取链表的长度而不需要额外的空间去存储这些结点：

  • 第一次遍历获取链表的元素个数
  • 第二次遍历直接找到第 N/2 个元素 ```c /**
    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
    • struct ListNode *next;
    • }; */

struct ListNode middleNode(struct ListNode head){ // 找出链表长度 int k = 0; struct ListNode *target = head; while(target) { k++; target = target->next; }

  1. int p = 1;
  2. // 找出中间位置
  3. int a = k/2+1;
  4. struct ListNode *temp = head;
  5. while (temp && p < a) {
  6.     temp = temp->next;
  7.     p++;
  8. }
  9. return temp;

} ```

  • 时间复杂度: O(N)
  • 空间复杂度: O(1)