链表的中间结点

[编程题]链表的中间结点

热度指数：1740 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

结点数量介于 1 和 100 之间。

示例1

输入

{1,2,3}

输出

{2,3}

说明

此列表中的中间为结点 2 ,测评系统对该结点序列化表述是 {2,3}

示例2

输入

{1,2,3,4}

输出

{3,4}

说明

此列表中的中间为结点 3 ,测评系统对该结点序列化表述是 {3,4}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

吾辈长歌

另类解法，

struct ListNode* middleNode(struct ListNode* head ) 
{
    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *p = dummy;
    struct ListNode *cur = dummy;
    int sz = 0;

    while(p->next)
    {
        sz++;
        p = p->next;
    }

    int mid = (sz / 2) + 1 ;

    for(int i=0;i<mid;i++)
    {
        cur = cur->next;
    }

    dummy->next = cur;
    return dummy->next;
}

不采用快慢指针，先求出链表的长度，除以2在+1就可以求出中间值，中间值前面的抛弃即可。

发表于 2023-04-13 00:23:05 回复(0)

阿金要努力

struct ListNode* middleNode(struct ListNode* head ) 
{
    // write code here
    struct ListNode* fast=head;
    struct ListNode* slow=head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

发表于 2022-04-19 16:56:56 回复(0)