【leetcode】链表的中间节点

一、题目描述

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

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

二、解题思路

2.1 暴力解法

判断特殊情况：节点数为1的情况 遍历链表，将链表节点存入集合(最好使用泛型，能够减少类型转换的开销)，记录链表长度。 根据count是单数还是双数来选择访问集合位置，但要注意集合是从0开始存的。

2.2 快慢指针

快慢指针不仅仅适用于这一类题，像环形链表、倒数第K个节点等都适用。 快慢指针的核心思想就是：两个指针同时走，一个走一步一个走两步，这样快指针走到最后时刻，慢指针恰好指向中间节点。 值得注意的是：你需要判断快指针是否为空、快指针的下一个节点是否为空、快指针的下下节点是否为空、以及快指针应该先走几步等等问题

三、代码题解

暴力解法：

/**
 * 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) {
          
   
        int count =1;
        List<ListNode> list =new ArrayList();
        if(head.next==null){
          
   
            return head;
        }
        while(true){
          
   
            //ListNode head1=head;
            //list中存放的引用直接指向堆内存，而并非是指向head，
            //所以head引用改变,并不会直接改变List集合中存放的元素。
            list.add(head);
            if(head.next!=null){
          
   
                head=head.next;
                count++;
                continue;
            }else{
          
   
                break;
            }
        }
        if(count%2==0){
          
   
            return list.get(count/2);
        }else{
          
   
            return list.get(count/2);
        }
    }
}

快慢指针：

/**
 * 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) {
          
   
        //快慢指针解法
        ListNode fastHead=head;
        ListNode slowHead=head;
        if(head.next==null){
          
   
            return head;
        }else if(head.next.next==null){
          
   
            return head.next;
        }
        else{
          
   
            while(true){
          
   
                slowHead=slowHead.next;
                fastHead=fastHead.next.next;
                if(fastHead.next!=null&&fastHead.next.next==null){
          
   
                    return slowHead.next;
                }else if(fastHead.next==null){
          
   
                    return slowHead;
                }
            }
        }
    }
}