LeetCode（Linked List)876. Middle of the Linked List

柔情只为你懂 2023-09-24 20:23 126阅读 0赞

# 1.问题 #

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:  
![在这里插入图片描述][5f0789ee2b1a49e994f0bd73e3806070.png]

> Input: head = \[1,2,3,4,5\]  
> Output: \[3,4,5\]  
> Explanation: The middle node of the list is node 3.

Example 2:  
![在这里插入图片描述][520d09732db243018cdd6ea270350dda.png]

> Input: head = \[1,2,3,4,5,6\]  
> Output: \[4,5,6\]  
> Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

*  The number of nodes in the list is in the range \[1, 100\].
 *  1 <= Node.val <= 100

# 2. 解题思路 #

## 方法1： ##

> 1.设定 两个指针，即指向链表头部的慢和快。  
> 2.运行一个while循环，直到fast的下一个节点不等于null并且fast的下一个节点的下一个不等于null。  
> 3.Fast会向右移动两个节点。  
> 4.Slow将向右移动一个节点。
> 
> 5.while循环结束时，慢节点指向中间节点。  
> ![在这里插入图片描述][ea8dbdc857a146c0b5ee89fd668e6645.png]

# 3. 代码 #

## 代码1： ##

/**
     * 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 slow=head,fast=head;//1.设定 两个指针，即指向链表头部的慢和快。
            while(fast!=null&&fast.next!=null){
         //2.运行一个while循环，直到fast的下一个节点不等于null并且fast的下一个节点的下一个不等于null。
                fast=fast.next.next;// 3.Fast会向右移动两个节点。
                slow=slow.next;//4.Slow将向右移动一个节点。
            }  
             //5.while循环结束时，慢节点指向中间节点。
            return slow;
        }
    }

### 本地代码运行 ###

package com.amy;
    
    
    import org.w3c.dom.ls.LSInput;
    
    import static java.util.Collections.sort;
    
    /**
     * @author: Amy
     * @create: 2023-02-19 20:58
     **/
    class LinkedList {
        
        static ListNode head;
        ListNode pre;
        public static ListNode middleNode(ListNode head) {
        
                ListNode slow=head,fast=head;
                while(fast!=null&&fast.next!=null){
        
                    fast=fast.next.next;
                    slow=slow.next;
                }
                ListNode pre=slow;
                return pre;
    
        }
        public static void push(int new_data) {
        
            ListNode new_node = new ListNode(new_data);
            new_node.next = head;
            head = new_node;
        }
        public void print(){
        
            ListNode node = head;
            while(node!=null){
        
                System.out.print(node.val+" ");
                node = node.next;
            }
    
        }
        public static void main (String[]args){
        
            LinkedList list = new LinkedList();
            list.push(1);
            list.push(3);
            list.push(8);
            list.push(4);
            System.out.println("\nCreated Linked list is:");
            list.print();
            System.out.println("\n");
            head=middleNode(head);
            list.print();
        }
        static class ListNode {
        
            int val;
            ListNode next;
            ListNode(int value){
        
                val = value;
                next=null;
            }
        }
    }

Created Linked list is:
    4 8 3 1 
    
    3 1

[5f0789ee2b1a49e994f0bd73e3806070.png]: https://img-blog.csdnimg.cn/5f0789ee2b1a49e994f0bd73e3806070.png
[520d09732db243018cdd6ea270350dda.png]: https://img-blog.csdnimg.cn/520d09732db243018cdd6ea270350dda.png
[ea8dbdc857a146c0b5ee89fd668e6645.png]: https://img-blog.csdnimg.cn/ea8dbdc857a146c0b5ee89fd668e6645.png