leetCode-链表的中间结点
LeetCode-链表的中间结点
题目描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点 如果有两个中间结点，则返回第二个中间结点。
思路:
-
方法一：java快慢指针
class Solution {
public ListNode middleNode(ListNode head) {
ListNode p = head, q = head;
while (q != null && q.next != null) {
q = q.next.next;
p = p.next;
}
return p;
}
}
-
方法二：单指针法
class Solution {
public ListNode middleNode(ListNode head) {
int n = 0;
ListNode cur = head;
while (cur != null) {
++n;
cur = cur.next;
}
int k = 0;
cur = head;
while (k < n / 2) {
++k;
cur = cur.next;
}
return cur;
}
}
