LeetCode876. 链表的中间结点🌟🌟🌟🌟🌟简单

算法系统课免费

问题描述

给你单链表的头结点 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

代码实现

Java

/**
 * 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 || head.next == null){
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;

    }

}

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head

        slow = head
        fast = head

        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next

        return slow

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    return slow
}

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # 双指针 class Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow

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

/** * 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; } * } */ // 【思路】单指针，遍历再折半 // 时间复杂度：O(n) // 空间复杂度：O(1) class Solution { public ListNode middleNode(ListNode head) { ListNode cnt = head; int count = 0; while(cnt != null) { count++; cnt = cnt.next; } if(count % 2 == 1) { count = (count + 1) / 2; } else { count /= 2; count++; } for(int i = 1; i < count; i++) { head = head.next; } return head; } } // 【思路】快慢指针 // 时间复杂度：O(n) // 空间复杂度：O(1) // class Solution { // public ListNode middleNode(ListNode head) { // ListNode fast = head; // ListNode slow = head; // while(fast != null && fast.next != null) { // fast = fast.next.next; // slow = slow.next; // } // return slow; // } // }

//链表的第二个中间节点 class Solution { public ListNode middleNode(ListNode head) { if(head == null) return null; ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } }

class Solution { public ListNode middleNode(ListNode head) { if(head == null) return null; int n = 0; ListNode cur = head; while(cur!=null){ cur = cur.next; n++; } int mid = n/2+1; for (int i = 1; i < mid; i++) { head = head.next; } return head; } }

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

发表回复取消回复

后才能评论

我来吃饭啦永久会员 2024年6月17日下午4:10

Mr.肖永久会员 2024年3月25日下午5:17

Yuki 永久会员 2024年1月27日上午11:48

打卡
https://leetcode.cn/problems/middle-of-the-linked-list/solutions/2621520/876-lian-biao-de-zhong-jian-jie-dian-by-4hhui

登录以回复

uu 永久会员 2023年9月19日下午3:23

阿尚普通 2023年8月17日上午10:41

3_🔥 永久会员 2023年7月9日下午10:00

第一次的笨蛋做法

快慢指针优化做法

帅气的冬瓜普通 2023年6月26日下午5:46

打卡

登录以回复

问题描述

代码实现

Java

Python

C++

Go

发表回复 取消回复

评论(7)

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复