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:
m nodes starting with the current node.n nodesReturn 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:
[1, 104].1 <= Node.val <= 1061 <= m, n <= 1000Follow up: Could you solve this problem by modifying the list in-place?
program main
use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
implicit none
integer, parameter :: n = 1000
type :: node
real(kind=DP), allocatable :: val(:)
class(node), pointer :: next => null()
end type node
type(node), pointer :: head, curr, prev
integer :: i, j, k, m, n
logical :: success
! Examples
call test_example1()
call test_example2()
contains
subroutine test_example1()
implicit none
type(node), pointer :: head, curr
integer :: i
real(kind=DP), allocatable :: vals(:)
allocate(head)
head%val = [1._DP, 2._DP, 3._DP, 4._DP, 5._DP, 6._DP, 7._DP, &
8._DP, 9._DP, 10._DP, 11._DP, 12._DP, 13._DP]
head%next => null()
do i = 1, size(head%val)
if (associated(head%next)) then
allocate(head%next)
head => head%next
else
exit
end if
end do
call traverse_and_remove(head, 2, 3)
write(*,*) "Example 1:"
write(*,*) "Input: ", head%val
write(*,*) "Output: ", head%val
write(*,*) ""
end subroutine test_example1
subroutine test_example2()
implicit none
type(node), pointer :: head, curr
integer :: i
real(kind=DP), allocatable :: vals(:)
allocate(head)
head%val = [1._DP, 2._DP, 3._DP, 4._DP, 5._DP, 6._DP, 7._DP, &
8._DP, 9._DP, 10._DP, 11._DP]
head%next => null()
do i = 1, size(head%val)
if (associated(head%next)) then
allocate(head%next)
head => head%next
else
exit
end if
end do
call traverse_and_remove(head, 1, 3)
write(*,*) "Example 2:"
write(*,*) "Input: ", head%val
write(*,*) "Output: ", head%val
write(*,*) ""
end subroutine test_example2
function traverse_and_remove(head, m, n) result(new_head)
implicit none
type(node), pointer, intent(inout) :: head
integer, value :: m, n
type(node), pointer :: new_head, curr, prev
integer :: i
new_head => head
curr => head
do i = 1, m
if (.not. associated(curr%next)) exit
curr => curr%next
end do
do while (associated(curr%next))
prev => curr
curr => curr%next
deallocate(prev%next)
do i = 1, n
if (.not. associated(curr%next)) exit
curr => curr%next
end do
end do
return
end function traverse_and_remove
end program maintemp.f95:10:28:
10 | integer :: i, j, k, m, n
| 1
Error: Symbol ‘n’ at (1) already has basic type of INTEGER
temp.f95:75:4:
67 | call traverse_and_remove(head, 1, 3)
| 2
......
75 | function traverse_and_remove(head, m, n) result(new_head)
| 1
Error: ‘traverse_and_remove’ at (1) has a type, which is not consistent with the CALL at (2)
temp.f95:75:4:
39 | call traverse_and_remove(head, 2, 3)
| 2
......
75 | function traverse_and_remove(head, m, n) result(new_head)
| 1
Error: ‘traverse_and_remove’ at (1) has a type, which is not consistent with the CALL at (2)
module linked_list
! Define the node structure
type node
integer :: val
type(node), pointer :: next => null()
end type
contains
! Function to remove nodes from the linked list
function remove_nodes(head, m, n) result(new_head)
type(node), pointer :: head, current, new_head
integer :: m, n
! Initialize the new head to null
new_head => null()
! If the head is null, return null
if (associated(head)) then
! Set the current node to the head
current => head
! Loop until the current node is null
do while (associated(current))
! If the current node is the first m nodes, set the new head
if (current == head .and. m > 0) then
new_head => current
end if
! If the current node is the first m nodes, set the new head
if (m > 0) then
m = m - 1
else
! If the current node is not the first m nodes, remove the next n nodes
do i = 1, n
if (associated(current%next)) then
current => current%next
else
exit
end if
end do
end if
! Set the current node to the next node
current => current%next
end do
end if
! Return the new head
remove_nodes = new_head
end function
end module
program test_linked_list
use linked_list
implicit none
! Declare the variables
type(node), pointer :: head, current
integer :: m, n
! Create the linked list
head => null()
current => head
do i = 1, 13
if (associated(current)) then
allocate(current%next)
current => current%next
else
allocate(head)
current => head
end if
current%val = i
end do
! Test the function with the first example
m = 2
n = 3
head => remove_nodes(head, m, n)
do while (associated(head))
write (*,*) head%val
head => head%next
end do
! Test the function with the second example
m = 1
n = 3
head => remove_nodes(head, m, n)
do while (associated(head))
write (*,*) head%val
head => head%next
end do
! Test the function with the third example
m = 2
n = 3
head => remove_nodes(head, m, n)
do while (associated(head))
write (*,*) head%val
head => head%next
end do
! Test the function with the fourth example
m = 1
n = 3
head => remove_nodes(head, m, n)
do while (associated(head))
write (*,*) head%val
head => head%next
end do
! Test the function with the fifth example
m = 2
n = 3
head => remove_nodes(head, m, n)
do while (associated(head))
write (*,*) head%val
head => head%next
end do
! Test the function with the sixth example
m = 1
n = 3
head => remove_nodes(head, m, n)
do while (associated(head))
write (*,*) head%val
head => head%next
end do
! Test the function with the seventh example
m = 2
n = 3
head => remove_nodes(head, m, n)
do while (associated(head))
write (*,*) head%val
head => head%next
end do
! Test the function with the eighth example
m = 1
n = 3
head => remove_nodes(head, m, n)
do while (associated(head))
write (*,*) head%
temp.f95:51:17:
51 | remove_nodes = new_head
| 1
Error: ‘remove_nodes’ at (1) is not a variable
temp.f95:27:16:
27 | if (current == head .and. m > 0) then
| 1
Error: Operands of comparison operator ‘==’ at (1) are TYPE(node)/TYPE(node)
temp.f95:57:9:
57 | use linked_list
| 1
Fatal Error: Cannot open module file ‘linked_list.mod’ for reading at (1): No such file or directory
compilation terminated.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def longestZigZag(root: TreeNode) -> int:
maxLen = [0]
def longestZigZagUtil(root, left):
if not root:
return -1
leftZig = longestZigZagUtil(root.left, True)
rightZig = longestZigZagUtil(root.right, False)
maxLen[0] = max(maxLen[0], max(leftZig, rightZig) + 1)
return rightZig + 1 if left else leftZig + 1
longestZigZagUtil(root, True)
longestZigZagUtil(root, False)
return maxLen[0]
The algorithm is a recursive depth-first search on the binary tree. The `longestZigZagUtil` function is called with two arguments: a tree node, and a boolean value indicating if the zigzag direction is left (`True`) or right (`False`).
For each recursive call, we calculate the zigzag lengths of the left and right child nodes by calling the utility function with left as True and False, respectively. We update the maximum zigzag length by comparing the current maximum length with the sum of the maximum lengths of the left and right child nodes, plus one.
The base case is when root is null (Python: None, Java: null, JavaScript: null), in which case we return -1 as the zigzag length.
Finally, we call the utility function for both left (True) and right (False) directions to find the maximum length and return it.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int longestZigZagUtil(TreeNode* root, bool left, int& maxLen) {
if (!root)
return -1;
int leftZig = longestZigZagUtil(root->left, true, maxLen);
int rightZig = longestZigZagUtil(root->right, false, maxLen);
maxLen = max(maxLen, max(leftZig, rightZig) + 1);
return left ? rightZig + 1 : leftZig + 1;
}
int longestZigZag(TreeNode* root) {
int maxLen = 0;
longestZigZagUtil(root, true, maxLen);
longestZigZagUtil(root, false, maxLen);
return maxLen;
}
The algorithm is a recursive depth-first search on the binary tree. The `longestZigZagUtil` function is called with two arguments: a tree node, and a boolean value indicating if the zigzag direction is left (`True`) or right (`False`).
For each recursive call, we calculate the zigzag lengths of the left and right child nodes by calling the utility function with left as True and False, respectively. We update the maximum zigzag length by comparing the current maximum length with the sum of the maximum lengths of the left and right child nodes, plus one.
The base case is when root is null (Python: None, Java: null, JavaScript: null), in which case we return -1 as the zigzag length.
Finally, we call the utility function for both left (True) and right (False) directions to find the maximum length and return it.