2. Linked List(with example problems)
1. Tools: Dummy Node
When to use:
- When it related to the head node, and the head node is uncertain.
Tips:
a. If a node->next is effected, then we need to correct this pointer.
b. If the node to be deleted is dynamically allocated memory, we need to reallocate these memory.
Code:
ListNode* dummy = new ListNode(0);
dummy->next = head;
Example:
- Given a linked list and a value x, write a function to reorder this list such that all nodes less than x come before the nodes greater than or equal to x.
- Create two dummy nodes, and divide list into two linked list. Finally, append larger one behind the smaller one.
2. Tools: Chaser-Runner
When to use:
- When we need to find the specific position of the list, e.g. the middle node.
Code:
ListNode* chaser= head, * runner = head;
while(chaser->next && runner->next->next){
chaser = chaser->next;
runner = runner->next->next;
}
Example:
- Find the middle point of linked list.
- Runner use the speed that twice faster than the chaser. When the runner reach the end, the chaser is at the middle node.
- Find the kth to last element of a singly linked list
- Runner is k position faster than chacser. When the runner reach the end, the chaser is at the last kth node.
- Circular Linked List Problem, see below.
3. Tools: Doubly Linked List in C++
Doubly Linked List in C++ is std::list< T>
Frequent iterator: begin(), end(), rbegin(), rend()
Frequent functions: empty(), size(), push_back(T value), pop_back(T value), erase(iterator pos), insert(iterator pos, T value).
4. Problem Type:
4.1. Operations in Iterating List
When iterating the linked list, each time only process one/pair nodes. The core node is the current node, or else it’s easily cause duplicate-process problem.
4.1.1. Examples:
372. Delete Node in a Linked List
void deleteNode(ListNode * node) {
// write your code here
if (node) {
node->val = node->next->val;
node->next = node->next->next;
}
}
class Solution {
public:
/**
* @param head: a ListNode
* @param k: An integer
* @return: a ListNode
*/
ListNode * reverseKGroup(ListNode * head, int k) {
// write your code here
// There are two main parts: repeated reverse Linked list, and the size would be k
ListNode* dummy = new ListNode(0);
dummy->next = head;
head = dummy;
while(head->next){
head = reverseNextK(head, k);
}
return dummy->next;
}
ListNode* reverseNextK(ListNode* head, int k){
// check if there is k nodes to be reversed
ListNode* nk = head;
for(int i = 0; i < k; i++){
if(!nk->next){
return nk;
}
nk = nk->next;
}
//Before: head->n1->n2->..->nk->..
//After : head->nk->nk-1->..->n1->..
ListNode* n1 = head->next;
ListNode* curr = n1, *next = curr->next;
for(int i = 0; i< k-1; i++){
if(!next){
n1->next = nullptr;
break;
}
ListNode* tmp = next->next;
next->next = curr;
curr = next;
next = tmp;
}
head->next = curr;
n1->next = next;
return n1;
}
};
ListNode * partition(ListNode * head, int x) {
// write your code here
ListNode* smaller = new ListNode(0);
ListNode* larger = new ListNode(0);
ListNode* n1 = smaller, *n2 = larger;
while(head){
ListNode* nxt = head ->next;
head ->next = nullptr;
if(head ->val < x){
n1 ->next = head;
n1 = n1 ->next;
} else {
n2 ->next = head;
n2 = n2 ->next;
}
head = nxt;
}
n1 ->next = larger ->next;
return smaller ->next;
}
4.2. Swap Nodes
If we want to swap two nodes(except deleting), their previous nodes and next nodes will be effected. However, under any circumstance, we can always do this without error:
a. Swap the value of both prvious_node->next
b. Swap the value of both node->next
4.2.1. Examples:
511. Swap Two Nodes in Linked List
As it’snot allowed to swap the value directly, we need to record the prev/post pointer of two value nodes.
One thing need to be mentioned is the corner cases:
- What if node not exist
- What if two nodes are previous-next relation.
ListNode * swapNodes(ListNode * head, int v1, int v2) {
// write your code here
if(!head)
return head;
ListNode* dummy = new ListNode(0);
dummy ->next = head;
ListNode *prev_v1 = dummy, *v1_ = dummy ->next, *post_v1;
while(v1_ && v1_ ->val != v1) {
post_v1 = v1_ ->next;
prev_v1 = v1_;
v1_ = post_v1;
}
post_v1 = v1_ ? v1_ ->next : nullptr;
ListNode *prev_v2 = dummy, *v2_ = dummy ->next, *post_v2;
while(v2_ && v2_ ->val != v2) {
post_v2 = v2_ ->next;
prev_v2 = v2_;
v2_ = post_v2;
}
post_v2 = v2_ ? v2_ ->next : nullptr;
if(! v1_ || !v2_)
return dummy ->next;;
if (post_v1 == v2_) {
prev_v1 ->next = v2_;
v2_ ->next = v1_;
v1_ ->next = post_v2;
return dummy ->next;
}
if (prev_v1 == v2_) {
prev_v2 ->next = v1_;
v1_ ->next = v2_;
v2_ ->next = post_v1;
return dummy ->next;
}
prev_v1 ->next = v2_;
prev_v2 ->next = v1_;
v1_ ->next = post_v2;
v2_ ->next = post_v1;
return dummy ->next;
}
36. Reverse Linked List II
For the special position, such as the previous node of M and post node of N, we need extra pointer to keep its position, in case of mistakes.
ListNode * reverseBetween(ListNode * head, int m, int n) {
// write your code here
if(m >= n || !head)
return head;
ListNode *dummy = new ListNode(0);
dummy ->next = head;
head = dummy;
for(int i = 0; i < m -1; i++){
if( !head)
return nullptr;
head = head ->next;
}
ListNode *premNode = head;
ListNode *mNode = head ->next;
ListNode *nNode = mNode, *postnNode = mNode ->next;
for(int i = m; i < n; i++) {
if(! postnNode )
return nullptr;
ListNode *tmp = postnNode ->next;
postnNode ->next = nNode;
nNode = postnNode;
postnNode = tmp;
}
mNode ->next = postnNode;
premNode ->next = nNode;
return dummy ->next;
}
4.3. Handling Two Node Simultaneously
When we handle two lists at the same time ,we could user while(l1 && l2), and then handle the non-nullptr list.
4.3.1. Examples:
ListNode * mergeTwoLists(ListNode * l1, ListNode * l2) {
// write your code here
ListNode* dummy = new ListNode(0);
ListNode *ptr = dummy;
while(l1 && l2){
if(l1->val <= l2 ->val){
ptr ->next = l1;
l1 = l1 ->next;
} else {
ptr ->next = l2;
l2 = l2 ->next;
}
ptr = ptr ->next;
}
while(l1)
{
ptr ->next = l1;
l1 = l1 ->next;
ptr = ptr ->next;
}
while(l2)
{
ptr ->next = l2;
l2 = l2 ->next;
ptr = ptr ->next;
}
return dummy ->next;
}
- Find the mid node using chaser-runner method
- Reverse the second part of the list
- Alternatively Merge two Lists.
void reorderList(ListNode * head) {
// write your code here
if(! head)
return;
ListNode *runner = head, *chaser = head;
while(runner ->next && runner ->next ->next) {
runner = runner ->next ->next;
chaser = chaser ->next;
}
if(runner == chaser)
return;
runner = chaser ->next;
chaser ->next = nullptr;
// reverse the latter part of the ListNode
ListNode * prev, * ptr, * nxt;
prev = runner;
ptr = prev ->next;
prev ->next = nullptr;
while(ptr) {
nxt = ptr ->next;
ptr ->next = prev;
prev = ptr;
ptr = nxt;
}
ptr = prev;
ListNode* dummy = new ListNode(0);
ListNode *node = dummy;
bool isAlter = false;
while(head && ptr) {
if(!isAlter) {
node ->next = head;
head = head ->next;
node = node ->next;
isAlter = !isAlter;
} else {
isAlter = !isAlter;
node ->next = ptr;
ptr = ptr ->next;
node = node ->next;
}
}
if(head)
node ->next = head;
if(ptr)
node ->next = ptr;
head = dummy ->next;
}
ListNode * rotateRight(ListNode * head, int k) {
// write your code here
if( ! head)
return head;
int len = 0;
ListNode *ptr = head;
while(ptr ) {
len ++;
ptr = ptr ->next;
}
k = k % len;
if(k == 0)
return head;
ListNode *fast = head;
for(int i = 0; i < k; i ++) {
fast = fast ->next;
}
ListNode *slow = head;
while(fast ->next) {
slow = slow ->next;
fast = fast ->next;
}
fast ->next = head;
head = slow ->next;
slow ->next = nullptr;
return head;
}
4.4. Recursion Problem
If the process of the current node is based on the next node, which is reversely traverse problem, we could use recursion, or stack.
4.4.1. Examples:
- Traverse the linked list reversely.
void traverse(ListNode* head)
{
if(head == nullptr)
return;
traverse(head->next);
visit(head);
}
106. Convert Sorted List to Binary Search Tree
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: a tree node
*/
TreeNode *sortedListToBST(ListNode *head) {
if (head == NULL) {
return NULL;
}
int size = getListSize(head);
return convertHelper(head, size);
}
int getListSize(ListNode *head) {
int size = 0;
while (head != NULL) {
head = head->next;
size++;
}
return size;
}
TreeNode *convertHelper(ListNode *&head, int size) {
if (size == 0) {
return NULL;
}
TreeNode *root = new TreeNode(0);
root->left = convertHelper(head, size / 2);
root->val = head->val; head = head->next;
root->right = convertHelper(head, size - size / 2 - 1);
return root;
}
};
4.5. Hash Map
To deep copy a list, we usually use hash map to relate the new node and old node.
4.5.1. Examples:
105. Copy List with Random Pointer
RandomListNode *copyRandomList(RandomListNode *head) {
// write your code here
if(! head)
return head;
unordered_map<RandomListNode*, RandomListNode*> hash;
RandomListNode *dummy = new RandomListNode(0);
RandomListNode *ptr = dummy, *curt = head;
while(curt) {
RandomListNode *new_node = new RandomListNode(curt ->label);
hash[curt] = new_node;
ptr ->next = new_node;
curt = curt ->next;
ptr = ptr ->next;
}
curt = head;
while(curt) {
hash[curt] ->random = curt->random? hash[curt ->random] : nullptr;
curt = curt ->next;
}
return dummy ->next;
}
Problem Discuss:
1. Circular Linked List
Examples:
- Given a linked list, determine if it has a cycle in it.
Based on the runner-chaser technique, let the runner use twice speed of the chaser. If there exists circle, the runner and chaser will meet at some position.
bool hasCycle(ListNode * head) {
// write your code here
if (!head || !head ->next)
return false;
ListNode *slow = head, *fast = head ->next;
while(slow != fast) {
if (!fast || ! (fast ->next) )
return false;
slow = slow ->next;
fast = fast ->next ->next;
}
return true;
}
- Given a circular linked list, return the node at the beginning of the loop.
Based on previous problem, let the runner use twice speed of the chaser. When they are first time met, move the chaser from the met position to the head, the second time they met is the beginning of the circle.
ListNode * detectCycle(ListNode * head) {
// write your code here
if(!head || ! head ->next)
return nullptr;
ListNode *slow = head, *fast = head ->next;
while(slow != fast) {
if( !fast || ! fast ->next)
return nullptr;
slow = slow ->next;
fast = fast ->next ->next;
}
while(head != slow ->next) {
slow = slow ->next;
head = head ->next;
}
return head;
}
2. Intersection of Two Singly Linked List
To determine whether exists the intersection of two linked list, we need to check whether two lists have circles.
1. If one have circle while the other don’t, they is no intersection.
2. If neither has circle, check if their end nodes are the same.
3. If both has circles, find the Z point(intersection of the circle) of a list, and check if this Z point is in the other list.
How to find the first intersection of two lists?
Get the length of two lists and the gap of two lists, and then, use chaser-runner. Let runner is gap-size faster than the chaser. The first place they met is the first intersection they have.