推 Jaka: 大師 10/14 16:25
推 Ericz7000: 大師 10/14 16:26
→ PogChampLUL: 大師 10/14 16:26
推 SiranuiFlare: 大師 10/14 16:27
推 pandix: 大師 10/14 16:28
推 thibw13ug1: 大師 10/14 16:31
推 wu10200512: 大師 10/14 17:03
2095. Delete the Middle Node of a Linked List
刪除鏈結串列中間的節點。
Exaple：
https://assets.leetcode.com/uploads/2021/11/16/eg1drawio.png
Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes
are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.
思路：
1.用龜兔賽跑法，快指針走到底的時候，慢指針會在中間節點。
2.因為要刪除節點需要知道該節點的前個節點，所以fast從第一個節點開始往後跑，prev
因為要比fast慢所以令他為dummy，當下個節點或當前節點為null的時候，慢指針會停
在要被刪除的節點之前。
3.把prev的下個節點刪除
4.返回dummy.next
Java Code：
class Solution {
public ListNode deleteMiddle(ListNode head) {
ListNode dummy = new ListNode(-1, head);
ListNode prev = dummy;
ListNode fast = head;
while (fast != null && fast.next != null) {
prev = prev.next;
fast = fast.next.next;
}
prev.next = prev.next.next;
return dummy.next;
}
}
https://i.imgur.com/S1WiNS3.png
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.111.108 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665735900.A.7A2.html