Problem: 876. 链表的中间结点
题目描述
思路
定义快慢指针fast、slow,fast每次走两步、slow每次一步,当fast指向链表尾节点时,slow指向链表的中间节点
复杂度
时间复杂度:
O ( n ) O(n) O(n);其中 n n n为单链表的长度
空间复杂度:
O ( 1 ) O(1) O(1)
Code
/**
* 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 {
/**
* Middle of the Linked List
*
* @param head The head of linked list
* @return ListNode
*/
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode solw = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
solw = solw.next;
}
return solw;
}
}