leetcode:那些年我遇到过的编程题009:链表的中间结点
程序员文章站
2022-03-13 21:25:43
...
leetcode:那些年我遇到过的编程题009:链表的中间结点先遍历链表计算节点数目,再将节点移至中间节点
/**
* 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 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;
}
}
还有一种快慢指针法,两个方法的时间复杂度都为O(n)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
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;
}
}