【Day 25 】2024-05-02 - 876. 链表的中间结点

[azl397985856]

876. 链表的中间结点

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/middle-of-the-linked-list/

前置知识

暂无

题目描述

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

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

 

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
 

提示：

给定链表的结点数介于 1 和 100 之间。

[hillsonziqiu]

思路

链表求中间值，那么就两个指针，一个指针跨2步，一个指针跨1步，当跨2步的指针到头之后，那么跨一步的指针正好指向中间。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
    let [p1, p2] = [head, head];
    while (p2 && p2.next) {
        p1 = p1.next;
        p2 = p2.next.next;
    }

    return p1;
};

复杂度分析

• 时间复杂度：O(n); 应该是链表长度的一半 n/2
• 空间复杂度：O(1); 只用到了两个变量

[xil324]

def middleNode(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

[CathyShang]

思路：

• 快慢指针，slow每次走1步，fast每次走2步，fast到链表尾部，正好slow到达中点；
• 设置虚拟头节点，当fast恰好到尾部时，那么slow->next为本题要求。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* preH = new ListNode(0);
        ListNode* slow = preH;
        ListNode* fast = preH;
        preH->next = head;
        while(fast->next!=nullptr&&fast->next->next!=nullptr){
            slow=slow->next;
            fast=fast->next;
            fast=fast->next;
        }
        return slow->next;
    }
};

• Time $O(N)$
• Space $O(1)$

[zhiyuanpeng]

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast, slow = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Time O(N) Space O(1)

[lxy1108]

思路

快慢指针，快指针走两步，慢指针走一步，直到快指针不能再走两步。如果停止时快指针后面没有节点，说明链表中有奇数个节点，此时慢节点为中间节点；如果停止时快指针后面还有一个节点，说明链表中有偶数个节点，此时慢节点为第一个中间节点，因此返回慢节点的下一个节点。

python3代码

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast,slow = head,head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        if not fast.next:
            return slow
        return slow.next

复杂度分析

时间复杂度o(n) 需要遍历链表，n为链表中节点个数

空间复杂度o(1)

[rao-qianlin]

思路：使用快慢指针

代码：

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

    }
}

复杂度

时间复杂度 O(N) 空间复杂度 不使用额外空间

[smallppgirl]

思路： 快慢指针 代码：

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head.next is None:
            return head
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

时间复杂 O(n) 空间复杂 O(1)

[Dtjk]

class Solution { public: ListNode middleNode(ListNode head) { ListNode slow=head, fast=head; while(fast != nullptr && fast->next != nullptr){ fast = fast->next->next; slow = slow->next; } return slow; } };

[atom-set]

思路

• 快慢指针法，快指针走 2 步，慢指针走 1 步
• 快指针最后一步走完 2 步，是偶数个节点，更新慢指针
• 快指针最后一步走不完 2 步，是奇数个节点，不更新
• 返回慢指针即可

代码

var middleNode = function (head) {
  if (!head || !head.next) {
    return head;
  }

  slow = head;
  fast = head;

  while (fast) {
    if (fast.next) {
      fast = fast.next.next;
    } else {
      fast = fast.next;
      break;
    }
    slow = slow.next;
  }

  return slow;
};

复杂度分析

时间复杂度花费在遍历链表上，故 O(N)

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