【問題描述】

給定一個帶有頭結點 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.快慢指針 時間復雜度：O(N) 空間復雜度：O(1)

class Solution {public ListNode middleNode(ListNode head) {ListNode slow=head;ListNode fast=head;while(fast!= null && fast.next!=null){ //快指針q每次走2步，慢指針p每次走1步，當q走到末尾時p正好走到中間。slow=slow.next;fast = fast.next.next;}return slow; } }

?###### 2. 數組 時間復雜度：O(N) 空間復雜度：O(N)

class Solution {public ListNode middleNode(ListNode head) {ListNode[] A = new ListNode[100];int t = 0;while (head != null) {A[t++] = head;head = head.next;}return A[t / 2];} }

?###### 3. 單指針法 時間復雜度：O(N) 空間復雜度：O(1)

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;} }

【總結】

鏈表刷題需要牢記快慢指針

鏈表的查詢效率低

鏈表題目打草稿很重要

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第876题][快慢指针]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。