203. Remove Linked List Elements
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0); // Create a dummy node to handle the case where the head node needs to be removed
dummy.next = head;
ListNode prev = dummy;
ListNode curr = head;
while (curr != null) {
if (curr.val == val) {
prev.next = curr.next; // Skip the current node
} else {
prev = curr; // Move the previous pointer forward
}
curr = curr.next; // Move the current pointer forward
}
return dummy.next; // Return the head of the modified linked list
}
}
two-pointer approach to traverse the linked list and remove nodes with the specified value.
time complexity O(n), space complexity O(1)
707. Design Linked List
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public class MyLinkedList {
ListNode head;
int size;
public MyLinkedList() {
head = null;
size = 0;
}
/**
* Get the value of the index-th node in the linked list.
* If the index is invalid, return -1.
*/
public int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.val;
}
/**
* Add a node of value val before the first element of the linked list.
* After the insertion, the new node will be the first node of the linked list.
*/
public void addAtHead(int val) {
ListNode newNode = new ListNode(val);
newNode.next = head;
head = newNode;
size++;
}
/**
* Append a node of value val to the last element of the linked list.
*/
public void addAtTail(int val) {
ListNode newNode = new ListNode(val);
if (head == null) {
head = newNode;
} else {
ListNode curr = head;
while (curr.next != null) {
curr = curr.next;
}
curr.next = newNode;
}
size++;
}
/**
* Add a node of value val before the index-th node in the linked list.
* If index equals to the length of the linked list, the node will be appended to the end of the linked list.
* If index is greater than the length, the node will not be inserted.
*/
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) {
return;
}
if (index == 0) {
addAtHead(val);
} else if (index == size) {
addAtTail(val);
} else {
ListNode newNode = new ListNode(val);
ListNode curr = head;
for (int i = 0; i < index - 1; i++) {
curr = curr.next;
}
newNode.next = curr.next;
curr.next = newNode;
size++;
}
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
if (index == 0) {
// If the list is empty, set the new node as the head
head = head.next;
} else {
ListNode curr = head;
for (int i = 0; i < index - 1; i++) {
curr = curr.next;
}
// Append the new node to the last node's next reference
curr.next = curr.next.next;
}
size--;
}
}
206. Reverse Linked List
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode reversed_head = reverseList(head.next);
head.next.next = head;
head.next = null;
return reversed_head;
}
}
//o(n), o(1)
