203. Remove Linked List Elements
Solution 1: # Simulation
/**
* 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) {
while(head != NULL && head->val == val){ // 处理头节点
ListNode* tmp = head;
head = head->next;
delete tmp;
}
ListNode* cur = head;
while(cur != NULL && cur->next != NULL){ //处理非头节点
if(cur->next->val == val){
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else cur = cur->next;
}
return head;
}
};Solution 2: # Dummyhead
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* cur = dummyhead;
while(cur->next != NULL){
if(cur->next->val == val) cur->next = cur->next->next;
else cur = cur->next;
}
head = dummyhead->next;
delete dummyhead;
return head;
}
};class MyLinkedList {
public:
struct ListNode{
int val;
ListNode* next;
ListNode(int val): val(val), next(nullptr){}
};
MyLinkedList() {
_dummyHead = new ListNode(0);
_size = 0;
}
int get(int index) {
if(index > (_size - 1) || index < 0) return -1;
ListNode* cur = _dummyHead->next;
while(index--) cur = cur->next;
return cur->val;
}
void addAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
void addAtTail(int val) {
ListNode* newNode = new ListNode(val);
ListNode* cur = _dummyHead;
while(cur->next != NULL) cur = cur->next;
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if(index > _size) return;
if(index < 0) index = 0;
ListNode* newNode = new ListNode(val);
ListNode* cur = _dummyHead;
while(index--) cur = cur->next;
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if(index >= _size || index < 0) return;
ListNode* cur = _dummyHead;
while(index--) cur = cur->next;
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
tmp = nullptr;
_size--;
}
private:
int _size;
ListNode* _dummyHead;
};Solution 1: # Two pointers
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tmp; // to record head's next node;
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur){
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};Solution 2 : # Recursion
class Solution {
public:
ListNode* reverse(ListNode* pre, ListNode* cur){
if(cur == nullptr) return pre; //递归终点
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(cur, tmp);
}
ListNode* reverseList(ListNode* head) {
return reverse(nullptr, head);
}
};Solution: # Dummyhead # Simulation
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr){
ListNode* tmp1 = cur->next;
ListNode* tmp2 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = tmp1;
cur->next->next->next = tmp2;
cur = cur->next->next;
}
return dummyHead->next;
}
};19. Remove Nth Node From End of List
Solution 1: # Tow pointers
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
for(int i = 0; i <= n; i++) fast = fast->next; // pre-adjust the fast pointer's position
while(fast != nullptr){ // move both slow & fast pointer at the same pace
slow = slow->next;
fast = fast->next;
}
ListNode* tmp = slow->next; // point the node to be removed
slow->next = slow->next->next; // link the next next node
delete tmp; // then delete the Nth node
return dummyHead->next;
}
};Solution 2: # Recursion
这个图很好的讲述了递归的原理！🐮最棒的方法
class Solution {
public:
int remove(ListNode* head, int n){
if(head == nullptr) return 0; // termination condition 递归终止条件
int steps = remove(head->next, n); // 往下一层递归
if(steps == n) head->next = head->next->next; // 找到了需要移除的点后进行操作
return steps+1; // 往上层递归
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(remove(head, n) == n) return head->next; // if head is the node we need to remove
return head;
}
};Solution 3: # Stack
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
stack<ListNode*> st;
int length = 0;
ListNode* tmp = head;
while(tmp){ // put all nodes in the stack and record the length
st.push(tmp);
tmp = tmp->next;
length++;
}
if(length == n) return head->next; // if head node is what we need to remove
while(n--){ // pop the last n nodes out of stack
st.pop();
}
tmp = st.top(); // the node before what we need to remove
tmp->next = tmp->next->next; // then remove
return head;
}
};160. Intersection of Two Linked Lists
Solution: # Two pointers # Simulation
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
while(curA){ // get the length of A
curA = curA->next;
lenA++;
}
while(curB){ // get the length of B
curB = curB->next;
lenB++;
}
// move these two pointers in the head;
curA = headA;
curB = headB;
// let curA points to the longer linked list
if(lenB > lenA){
swap(lenB, lenA);
swap(curA, curB);
}
int gap = lenA - lenB;
while(gap--) curA = curA->next; // adjust the position of curA
while(curA){ // then move both pointers at the same pace
if(curA == curB) return curA; // find the intersaction
curA = curA->next;
curB = curB->next;
}
return nullptr; // no intersaction
}
};Solution: # Two pointers
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
if(slow == fast){
ListNode* index1 = head;
ListNode* index2 = fast;
while(index1 != index2){
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return nullptr;
}
};