给定一个带有头结点 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
之间。
1.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
int num=0;
ListNode l1=head;
while(l1!=null)
{
num++;
l1=l1.next;
}
num=num/2;
while(num!=0){
head=head.next;
num--;
}
return head;
}
}
2.可以用数组记录下链表遍历的个数,直接除以2来得到中间结点,直接返回
class Solution {
public ListNode middleNode(ListNode head) {
ListNode[] A = new ListNode[100];
int t = 0;
while (head.next != null) {
A[t++] = head;
head = head.next;
}
return A[t / 2];
}
}
3.快慢指针法
当用慢指针 slow
遍历列表时,让另一个指针 fast
的速度是它的两倍。当 fast
到达列表的末尾时,slow
必然位于中间。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}