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