## Tricks to solve linked list¶

### Iterate tricks¶

• trick 1: If the iteration is for two linked lists with different length. You can use while (l1 || l2), inside the while loop, you can maintain the loop invariance by checking the nullptr and considering all edge cases.

## Catergory 1 Iterate linked lists¶

• Think about how to make the iteration elegant without dealing many if else conditions
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(INT_MIN);
ListNode *prev = &dummy;

int sum = 0;
while (l1 || l2 || sum) {
sum += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
ListNode *node = new ListNode(sum % 10);
prev->next = node;
prev = node;
l1 = l1 ? l1->next : l1;
l2 = l2 ? l2->next : l2;
sum /= 10;
}

return dummy.next;
}
};

• It seems we need a stack. We can use a stack variable or use recursion.
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1, s2;
while(l1) {
s1.push(l1->val);
l1 = l1->next;
}
while(l2) {
s2.push(l2->val);
l2 = l2->next;
}

int sum = 0;
ListNode *p = nullptr, *head = new ListNode(0);
while (!s1.empty() || !s2.empty()) {
if (!s1.empty()) { sum += s1.top(); s1.pop(); }
if (!s2.empty()) { sum += s2.top(); s2.pop(); }
p = new ListNode(sum / 10);
sum /= 10;
}

}
};

• We need a stack. Using recursion can help us handle the case well
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int carry = 0;

if (carry > 0) {
ListNode* node = new ListNode(carry);
}
}

// carry can also be passed by return value
void helper(ListNode* head, int& carry) {
// base case
carry = (tmp + 1 + carry) / 10;
return;
}

if (carry > 0) {
carry = (tmp + carry) / 10;
}
}
};

## Catergory 2 Remove nodes from linked lists¶

### Remove Nth Node From End of List¶

• use slow and fast node to "measure" the nth node and remove it.
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(INT_MIN);
ListNode *slow = &dummy;
ListNode *fast = &dummy;

while (n > 0) {
fast = fast->next;
n--;
}

while (fast->next) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;

return dummy.next;
}
};

• This is an easy problem, but can you use two * programing to solve it?
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode dummy(0);
ListNode *curr = &dummy;

while (curr->next) {
if (curr->next->val == val) {
ListNode *next = curr->next;
curr->next = next->next;
} else {
curr = curr->next;
}
}

return dummy.next;
}
};
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// if (head == nullptr) return nullptr;

while (*curr != NULL) {
ListNode *entry = *curr;
if (entry->val == val) {
*curr = entry->next;
} else {
curr = &(entry->next);
}
}

}
};

### Remove Duplicates from Sorted List¶

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while (curr) {
if (curr->val == prev->val) {
curr = curr->next;
prev->next = curr;
} else {
curr = curr->next;
prev = prev->next;
}
}

}
};

### Remove Duplicates from Sorted List II¶

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
if (head == nullptr) return nullptr;
ListNode dummy(INT_MIN);
ListNode *prev = &dummy;

while (curr) {
if (curr->next && curr->val == curr->next->val) {
int tmp = curr->val;
while (curr && curr->val == tmp) {
curr = curr->next;
}
prev->next = curr;
} else {
prev = curr;
curr = curr->next;
}
}

return dummy.next;
}
};

## Catergory 3 Reverse linked lists¶

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:

}

}
};
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
if (head == nullptr) return nullptr;

while(curr->next) {
ListNode *tmp = curr->next;
curr->next = tmp->next;
}

}
};
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:

}
};

## Catergory 5 Cycle in linked lists¶

### 708. Insert into a Sorted Circular Linked List¶

• What the loop invariant?
• It is easy to handle the common case prev <= insertVal <= curr.
• For the special case when "wrap around" the circle, it could be insertVal is the max or min, but in both cases, the insertion operation is the same.
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
"""

class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
node = Node(insertVal)
node.next = node
return node

while not prev.val <= insertVal <= curr.val and not prev.val > curr.val > insertVal and not insertVal > prev.val > curr.val:
prev, curr = prev.next, curr.next
break

prev.next = node
node.next = curr

/*
// Definition for a Node.
class Node {
public:
int val = NULL;
Node* next = NULL;

Node() {}

Node(int _val, Node* _next) {
val = _val;
next = _next;
}
};
*/
class Solution {
public:
Node* insert(Node* head, int insertVal) {
}

while (!(prev->val <= insertVal && insertVal <= next->val)
&& !(prev->val > next->val && insertVal < next->val)
&& !(prev->val > next->val && insertVal > prev->val)) {
prev = prev->next;
next = next->next;
break;
}

prev->next = new Node(insertVal, next);