Table of Contents
Introduction
- Remove Linked List Elements (LeetCode--203)
- Design Linked List (LeetCode--707)
- Reverse Linked List (LeetCode--206)
- Swap Nodes in Pairs (LeetCode--24)
- Remove Nth Node From End of List (LeetCode--19)
- Linked List Cycle II (LeetCode--142)
Introduction
Following the Code Thinking Record series, this article explores various linked list algorithm problems and captures key learning points.
- Remove Linked List Elements (LeetCode--203)
[1] Problem Description:
[2] Approach: Check if the next node's value matches the target value, and if so, adjust the current node's next pointer to skip the next node. To simplify operations, use a dummy head node.
[3] C++ Implementation:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
struct ListNode* dummy = new ListNode(0, head);
struct ListNode* current = dummy;
while (current->next) {
if (current->next->val == val) {
auto temp = current->next;
current->next = current->next->next;
delete temp;
} else {
current = current->next;
}
}
auto result = dummy->next;
delete dummy;
return result;
}
};
[4] Time Complexity: O(N), single traversal of the list.
[5] Space Complexity: O(1), only a dummy node is allocated.
- Design Linked List (LeetCode--707)
[1] Problem Description:
[2] Approach: This problem is straightforward with no major challenges. Most operations involve finding the node before the target index and then performing insertions or deletions.
[3] C++ Implementation:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class MyLinkedList {
private:
int length;
ListNode *first;
public:
MyLinkedList() {
this->length = 0;
this->first = new ListNode(0);
}
int get(int index) {
if (index >= this->length || index < 0)
return -1;
ListNode *current = first->next;
for (int i = 0; i < index; ++i) {
current = current->next;
}
return current->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(this->length, val);
}
void addAtIndex(int index, int val) {
if (index > this->length || index < 0)
return;
ListNode *prev = first;
for (int i = 0; i < index; ++i) {
prev = prev->next;
}
ListNode *temp = new ListNode(val, prev->next);
prev->next = temp;
this->length++;
}
void deleteAtIndex(int index) {
if (index >= this->length || index < 0)
return;
ListNode *prev = first;
for (int i = 0; i < index; ++i) {
prev = prev->next;
}
ListNode *temp = prev->next;
prev->next = prev->next->next;
delete temp;
this->length--;
}
};
[4] Time Complexity: get() is O(index), addAtHead() is O(1), addAtTail() is O(N), addAtIndex() is O(index), deleteAtIndex() is O(index).
[5] Space Complexity: O(1).
- Reverse Linked List (LeetCode--206)
[1] Problem Description:
[2] Approach: Traverse the given single-linked list and re-link each node to a new list using a head-insertion method.
[3] C++ Implementation:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *newHead = NULL;
ListNode *current = head;
while (current) {
head = current->next;
current->next = newHead;
newHead = current;
current = head;
}
return newHead;
}
};
[4] Time Complexity: O(N), single traversal of the list.
[5] Space Complexity: O(1).
- Swap Nodes in Pairs (LeetCode--24)
[1] Problem Description:
[2] Approach: Traverse the list and modify the next pointers according to the requirement. Use a pre pointer pointing to a dummy head and a current pointer pointing to pre->next. Modify the next pointers of pre and current accordingly, ensuring not to lose references to subsequent nodes. After processing, update pointers: pre = current and current = pre->next.
[3] C++ Implementation:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *dummy = new ListNode(0, head);
head = dummy;
ListNode* prev = dummy, *current = dummy->next;
while (current && current->next) {
prev->next = current->next;
ListNode* temp = current->next->next;
current->next->next = current;
current->next = temp;
prev = current;
current = prev->next;
}
head = dummy->next;
delete dummy;
return head;
}
};
[4] Time Complexity: O(N), single traversal of the list.
[5] Space Complexity: O(1).
- Remove Nth Node From End of List (LeetCode--19)
[1] Problem Description:
[2] Approach: Two-pointer technique. Move the fast pointer n+1 steps ahead, then move both pointers until fast reaches NULL. At that point, slow points to the node before the one to delete. Perform the deletion operation.
[3] C++ Implementation:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
ListNode* slow = dummy, *fast = dummy;
for (int i = 0; i < n + 1; ++i) {
fast = fast->next;
}
while (fast) {
slow = slow->next;
fast = fast->next;
}
ListNode* temp = slow->next;
slow->next = slow->next->next;
delete temp;
head = dummy->next;
delete dummy;
return head;
}
};
[4] Time Complexity: O(N), single traversal.
[5] Space Complexity: O(1).
[6] Insight: When seeking the nth element from the end of a single-linked list, utilize the two-pointer technique.
- Linked List Cycle II (LeetCode--142)
[1] Problem Description:
[2] Approach: Use two pointers. Fast moves two steps, slow moves one step. If they meet, there's a cycle; if fast reaches the end, there's no cycle. When a cycle exists, start one pointer from the beginning and another from the meeting point. Their next meeting point is the entry to the cycle.
[3] C++ Implementation:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};
[4] Time Complexity: O(N)
[5] Space Complexity: O(1)