Thủ Thuật Hướng dẫn Remove linked list elements Java Mới Nhất

Cập Nhật: 2022-01-16 04:12:05,Bạn Cần kiến thức và kỹ năng về Remove linked list elements Java. You trọn vẹn có thể lại phản hồi ở cuối bài để Ad đc tương hỗ.

745

Twitter2FacebookLinkedInBufferRedditTumblr2SHARES

Table of Contents

Tóm lược đại ý quan trọng trong bài

  • Problem Statement
  • Approach (Recursive)
  • Implementation of Remove Linked List Elements Leetcode Solution
  • Complexity Analysis of Number Complement Leetcode Solution
  • Approach (Iterative)
  • Implementation of Remove Linked List Elements Leetcode Solution
  • Complexity Analysis of Remove Linked List Elements Leetcode Solution

  • Problem Statement
    • Example
  • Approach (Recursive)
    • Implementation of Remove Linked List Elements Leetcode Solution
      • C++ Program
      • Java Program
    • Complexity Analysis of Number Complement Leetcode Solution
      • Time Complexity
      • Space Complexity
  • Approach (Iterative)
    • Implementation of Remove Linked List Elements Leetcode Solution
      • C++ Program
      • Java Program
    • Complexity Analysis of Remove Linked List Elements Leetcode Solution
      • Time Complexity
      • Space Complexity

Problem Statement

In this problem, we are given a linked list with its nodes having integer values. We need to delete some nodes from the list which have value equal to val.The problem does not require to be solved in-place but we will discuss one such approach.

Example

List = 1 -> 2 -> 2 -> 3 -> 4 , val = 21 3 4List = 2 -> 2 -> 2 -> 2 , val = 2Empty List

Pin

Approach (Recursive)

We can recursively call the same function to return the head of the required list. We achieve this by calling the function on subsequent suffixes of the given list with some conditions. However, we need to handle the base case when the list is empty. There is only one special case:

If the head of the list has a value equal to val(input), then, we need to return the function called on its next node. This is done to avoid the current node to be appended to the previous nodes of the list (as the function stack is completed).

Implementation of Remove Linked List Elements Leetcode Solution

C++ Program#include
using namespace std;
struct listNode

int value;
listNode* next;
listNode(int x)

value = x;
next = NULL;

;
void print(listNode* head)

if(head == NULL)
cout << "Empty Listn";
return;

while(head)

cout <value <next;

cout <value == val)
listNode* temp = head->next;
head->next = NULL;
delete(head);
return removeElements(temp , val);

head->next = removeElements(head->next , val);
return head;

int main()
listNode* head = new listNode(1);
head->next = new listNode(2);
head->next->next = new listNode(2);
head->next->next->next = new listNode(3);
head->next->next->next->next = new listNode(4);
int val = 2;
print(removeElements(head , val));
return 0;
Java Programclass listNode

int value;
listNode next;
listNode(int x)

value = x;
next = null;

;
class remove_linked_list_elements
public static void print(listNode head)
if(head == null)
System.out.println(“Empty List”);
return;

while(head != null)

System.out.print(head.value + ” “);
head = head.next;

System.out.println();
return;

public static listNode removeElements(listNode head, int val)
if(head == null)
return head;

if(head.value == val)
return removeElements(head.next , val);

head.next = removeElements(head.next , val);
return head;

public static void main(String args[])
listNode head = new listNode(1);
head.next = new listNode(2);
head.next.next = new listNode(2);
head.next.next.next = new listNode(3);
head.next.next.next.next = new listNode(4);
int val = 2;
print(removeElements(head , val));

1 3 4

Complexity Analysis of Number Complement Leetcode Solution

Time Complexity

O(N), where N = length of the list. We visit each element only once in the worst case.

See alsoKoko Eating Bananas Leetcode SolutionSpace Complexity

O(1). As the code follows tail recursion.

Approach (Iterative)

In order to delete any node, we need to have the address of its previous node, so that we can make the previous point to its next. This gives an idea to maintain a previous pointer that will help us to manipulate pointers in the list. Now, the important point is that the first node in the list does not have any previous node. So, we need to add a sentinel node in the beginning of the list. Now, we can traverse through the first node in the list(node next to sentinel node) and would face following two conditions:

1.) node->value == val: In this case, we will set prev->next = node->next.This will connect the previous of the current node with the next of the current node, and delete the current node using: delete(currentNode)

2.) Otherwise, we just set prev = headfor upcoming nodes.

At the end, the next of sentinel is the required list.

Implementation of Remove Linked List Elements Leetcode Solution

C++ Program#include
using namespace std;
struct listNode

int value;
listNode* next;
listNode(int x)

value = x;
next = NULL;

;
void print(listNode* head)

if(head == NULL)
cout << "Empty Listn";
return;

while(head)

cout <value <next;

cout <next = head;
while(head != NULL)
if(head->value == val)
toDelete = head;
prev->next = head->next;
head = head->next;
toDelete->next = NULL;

else
toDelete = NULL;
prev = head;
head = head->next;

if(toDelete != NULL)
delete(toDelete);

return dummy->next;

int main()
listNode* head = new listNode(1);
head->next = new listNode(2);
head->next->next = new listNode(2);
head->next->next->next = new listNode(3);
head->next->next->next->next = new listNode(4);
int val = 2;
print(removeElements(head , val));
return 0;
Java Programclass listNode

int value;
listNode next;
listNode(int x)

value = x;
next = null;

;
class remove_linked_list_elements
public static void print(listNode head)
if(head == null)
System.out.println(“Empty List”);
return;

while(head != null)

System.out.print(head.value + ” “);
head = head.next;

System.out.println();
return;

public static listNode removeElements(listNode head, int val)
listNode dummy = new listNode(-1) , prev = dummy , toDelete;
dummy.next = head;
while(head != null)
if(head.value == val)
prev.next = head.next;

else
prev = head;

head = head.next;

return dummy.next;

public static void main(String args[])
listNode head = new listNode(1);
head.next = new listNode(2);
head.next.next = new listNode(2);
head.next.next.next = new listNode(3);
head.next.next.next.next = new listNode(4);
int val = 2;
print(removeElements(head , val));

1 3 4

Complexity Analysis of Remove Linked List Elements Leetcode Solution

Time Complexity

O(N), as we iterate the whole list once. N = length of the list

See alsoMerge Sorted ArraySpace Complexity

O(1), as we only constant memory space.

Twitter2FacebookLinkedInBufferRedditTumblr2SHARES

Reply
1
0
Chia sẻ

đoạn Clip hướng dẫn Chia Sẻ Link Down Remove linked list elements Java ?

– Một số Keyword tìm kiếm nhiều : ” đoạn Clip hướng dẫn Remove linked list elements Java tiên tiến và phát triển nhất , Share Link Down Remove linked list elements Java “.

Giải đáp vướng mắc về Remove linked list elements Java

Quý quý khách trọn vẹn có thể để lại Comment nếu gặp yếu tố chưa hiểu nha.
#Remove #linked #list #elements #Java