You are given the head
of a linked list. Delete the middle node, and return the head
of the modified linked list.
The middle node of a linked list of size n
is the ⌊n / 2⌋th
node from the start using 0-based indexing, where ⌊x⌋
denotes the largest integer less than or equal to x
.
- For
n
=1
,2
,3
,4
, and5
, the middle nodes are0
,1
,1
,2
, and2
, respectively.
Example 1:
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.
Example 2:
Input: head = [1,2,3,4] Output: [1,2,4] Explanation: The above figure represents the given linked list. For n = 4, node 2 with value 3 is the middle node, which is marked in red.
Example 3:
Input: head = [2,1] Output: [2] Explanation: The above figure represents the given linked list. For n = 2, node 1 with value 1 is the middle node, which is marked in red. Node 0 with value 2 is the only node remaining after removing node 1.
Constraints:
- The number of nodes in the list is in the range
[1, 105]
. 1 <= Node.val <= 105
删除链表的中间节点。
给你一个链表的头节点 head 。删除 链表的 中间节点 ,并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点(下标从 0 开始),其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
对于 n = 1、2、3、4 和 5 的情况,中间节点的下标分别是 0、1、1、2 和 2 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题考察的链表的快慢指针,类似876题。唯一的不同点是876题请你返回的是链表中间的那个节点,所以走到中间那个节点之后就可以返回了。但是这道题让你返回的是去掉中间节点之后剩余的部分,返回的是头结点。虽然也是快慢指针的思路,但是这里我们还需要一个额外的 ListNode 记录 slow 指针的上一个位置。当 fast 指针跑完整个链表的时候,slow 指针指向的是中间的那个节点,但是我们需要的是 slow 节点的上一个节点,这样才能把 slow 指针指向的中间节点跳过。
时间O(n)
空间O(n)
Java实现
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode() {} 7 * ListNode(int val) { this.val = val; } 8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; } 9 * } 10 */ 11 class Solution { 12 public ListNode deleteMiddle(ListNode head) { 13 // corner case 14 if (head == null || head.next == null) { 15 return null; 16 } 17 18 // normal case 19 ListNode dummy = new ListNode(0); 20 dummy.next = head; 21 ListNode fast = head; 22 ListNode slow = head; 23 ListNode prev = null; 24 while (fast != null && fast.next != null) { 25 prev = slow; 26 slow = slow.next; 27 fast = fast.next.next; 28 } 29 prev.next = prev.next.next; 30 return dummy.next; 31 } 32 }
相关题目
876. Middle of the Linked List
2095. Delete the Middle Node of a Linked List
标签:Node,node,head,ListNode,list,List,next,节点,LeetCode From: https://www.cnblogs.com/cnoodle/p/16795572.html