首页 > 其他分享 >876. 链表的中间结点

876. 链表的中间结点

时间:2023-04-02 11:48:49浏览次数:48  
标签:结点 ListNode val 876 head next 链表 int

876. 链表的中间结点

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

方法一:快慢指针遍历

/**
 * 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 fast = new ListNode(-1,head);
        ListNode slow = new ListNode(-1,head);
 
        while (fast.next != null && fast.next.next !=null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow.next;
        
    }
}

方法二:先遍历一编记录长度,再遍历一次到中间节点,return 中间节点

/**
 * 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 dummy = new ListNode(-1,head);
        ListNode cur = dummy;
        int len = 0;
 
        while (cur.next!=null) {
            cur = cur.next;
            len++;
        }
        int n = len/2;
        while (n > 0) {
            n--;
            dummy = dummy.next;
        }

        return dummy.next;
    }
}

 

标签:结点,ListNode,val,876,head,next,链表,int
From: https://www.cnblogs.com/fulaien/p/17280141.html

相关文章

  • 23. 合并 K 个升序链表
    23.合并K个升序链表给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。示例1:输入:lists=[[1,4,5],[1,3,4],[2,6]]输出:[1,1,2,3,4,4,5,6]解释:链表数组如下:[1->4->5,1->3->4,2->6]将它们合并到一个有序链......
  • 洛谷 P8762 [蓝桥杯 2021 国 ABC] 123 题解
    为什么可以使用前缀和,这里提供解释:初读题目,我们发现这个数列很迷惑,似乎不能使用数学方法来解。\[1,1,2,1,2,3,1,2,3,4,\cdots\]但是,我们可以想到数形结合的方式,我们将数列看作一个三角形,于是他变成了:\[1\]\[1,2\]\[1,2,3\]\[1,2,3,4\]\[\cdots\cdots\]于是本题变得好思......
  • 链表完成多项式乘法
    多项式乘法是在多项式加法的基础上完成的。1、多项式加法1#include<iostream>2usingnamespacestd;3typedefstructlnode{4intcoef;5intexp;6lnode*next;7}lnode;8classpoly{9lnode*head;10public:11voidcreate(in......
  • 21. 合并两个有序链表
     21. 合并两个有序链表做法1:构建虚拟头节点,而后双指针做法。/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx):val(x),next(nullptr){}......
  • leetcode876. 链表的中间结点
      876. 链表的中间结点方法一:最简单的做法,先求出整个链表的长度,再求1/2处节点的位置。/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx)......
  • 反转链表-leetcode92
    给你单链表的头指针head和两个整数left和right,其中left<=right。请你反转从位置left到位置right的链表节点,返回反转后的链表。示例1:输入:head=[1,2,3,4,5],left=2,right=4输出:[1,4,3,2,5]示例2:输入:head=[5],left=1,right=1输出:[5]//leet......
  • 2023-03-21-将指针所在地址传入函数来创建链表的一种写法
    如下,通过将指针所在的地址传入函数中即**p的形式,来保证直接对地址进行运算,而不需要再返回一个链表//双链表#include<stdio.h>#include<stdbool.h>#include<malloc.h>typedefstructDNode{intdata;structDNode*prior,*next;//prior指向上一个结点,next指......
  • 【LBLD】如何判断回文链表
    【LBLD】如何判断回文链表判断回文单链表/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx):val(x),next(nullptr){}*ListNode(intx,......
  • Leetcode19. 删除链表的倒数第 N 个结点
     19. 删除链表的倒数第N个结点自己纯手写第一题,递归有点冗杂,开辟了虚拟头节点,而且要特别注意边界条件(当倒数第n个正好是头节点时)。***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),n......
  • LeetCode 222.完全二叉树的结点个数
    1.题目:给你一棵完全二叉树的根节点root,求出该树的节点个数。完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层,则该层包含1~ 2h 个节点。示例1:输入:root=[1......