You are given the head of a linked list and two integers m and n.
Traverse the linked list and remove some nodes in the following way:
Start with the head as the current node.
Keep the first m nodes starting with the current node.
Remove the next n nodes
Keep repeating steps 2 and 3 until you reach the end of the list.
Return the head of the modified list after removing the mentioned nodes.
Example 1:
Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
Output: [1,2,6,7,11,12]
Explanation: Keep the first (m = 2) nodes starting from the head of the linked List (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.
Example 2:
Input: head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3
Output: [1,5,9]
Explanation: Head of linked list after removing nodes is returned.
Constraints:
The number of nodes in the list is in the range [1, 104].
1 <= Node.val <= 106
1 <= m, n <= 1000
Follow up: Could you solve this problem by modifying the list in-place?
Solutions
Solution 1: Simulation
We can simulate the entire deletion process. First, use a pointer $\textit{pre}$ to point to the head of the linked list, then traverse the linked list, moving $m - 1$ steps. If $\textit{pre}$ is null, it means the number of nodes from the current node is less than $m$, so we directly return the head. Otherwise, use a pointer $\textit{cur}$ to point to $\textit{pre}$, then move $n$ steps. If $\textit{cur}$ is null, it means the number of nodes from $\textit{pre}$ is less than $m + n$, so we directly set the $\textit{next}$ of $\textit{pre}$ to null. Otherwise, set the $\textit{next}$ of $\textit{pre}$ to the $\textit{next}$ of $\textit{cur}$, then move $\textit{pre}$ to its $\textit{next}$. Continue traversing the linked list until $\textit{pre}$ is null, then return the head.
The time complexity is $O(n)$, where $n$ is the number of nodes in the linked list. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9101112131415161718192021
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defdeleteNodes(self,head:ListNode,m:int,n:int)->ListNode:pre=headwhilepre:for_inrange(m-1):ifpre:pre=pre.nextifpreisNone:returnheadcur=prefor_inrange(n):ifcur:cur=cur.nextpre.next=NoneifcurisNoneelsecur.nextpre=pre.nextreturnhead
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcdeleteNodes(head*ListNode,mint,nint)*ListNode{pre:=headforpre!=nil{fori:=0;i<m-1&&pre!=nil;i++{pre=pre.Next}ifpre==nil{returnhead}cur:=prefori:=0;i<n&&cur!=nil;i++{cur=cur.Next}pre.Next=nilifcur!=nil{pre.Next=cur.Next}pre=pre.Next}returnhead}