Linked list questions: https://leetcode.com/tag/linked-list/

1. Linked List

1.1 Delete/Insert

LC237: Delete node in a linked list

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

 
void deleteNode(ListNode* node){
  if(node == nullptr) return;
  ListNode *p=node;
  while(p->next != nullptr) {
    p->val = p->next->val;
    if(p->next->next == nullptr) break;
    p = p->next;
  }//--while
  delete p->next;
  p->next = nullptr;
}

LC203: Remove linked list elements

Remove all elements from a linked list of integers that have value val.

 
ListNode* removeElements(ListNode* head, int val) {
  if(head == nullptr) return head;
        
  ListNode* dummy = new ListNode(INT_MIN);
  dummy->next = head;
  ListNode *pre=dummy, *cur=head;
  while(cur != nullptr) {
    ListNode* next = cur->next;
    if(cur->val == val) {
      pre->next = cur->next;
      delete(cur);
    } else {
      pre = cur;
    }
    cur = next;
  }//--while
  head = dummy->next; delete(dummy);
  return head;
}

LC83: Remove duplicates from sorted list

Given a sorted linked list, delete all duplicates such that each element appear only once.

 
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr) return head;
        
        ListNode* dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode *p = dummy;
        while(p!=nullptr && p->next!=nullptr) {
            int val = p->next->val;
            if(val != p->val) {
                data.insert(val);
                p = p->next;
            } else {            //duplicate, remove
                delete(p->next);
                p->next = p->next->next;
            }
        }//--while
        return dummy->next;
    }

LC82: Remove duplicates from sorted list II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

 
   //looking forward further
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr) return head;
        ListNode* dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode* p = dummy;
        while(p->next!=nullptr && p->next->next!=nullptr) {
            if(p->next->val == p->next->next->val) {        //duplicate
                int mark = p->next->val;                    //mark the value
                ListNode* tmp = p->next;
                //keep removing
                while(tmp!=nullptr && tmp->val==mark) {
                    delete(tmp);
                    tmp = tmp->next;
                }
                p->next = tmp;
            } else {
                p = p->next;
            }
        }//--while
        return dummy->next;
    }

1.2 Reverse

LC206: Reverse linked list

Reverse a singly linked list.

 
//iterative, with new head
ListNode* reverseList(ListNode* head){
  if(head == nullptr) return head;
  ListNode* p = head;
  ListNode* dummy = new ListNode(INT_MIN);
  while(p != nullptr) {
    ListNode* tmp = p->next;
    p->next = dummy->next;
    dummy->next = p;
    p = tmp;
  }//--while
  return dummy->next;
}

 
//iterative, without new head
ListNode* reverseList(ListNode* head){
  if(head == nullptr) return head;
  ListNode* pre = nullptr;
  ListNode* p = head;
  while(p != nullptr){
    ListNode* next = p->next;
    p->next = pre;
    pre = p;
    p = next;
  }//--while
  return pre;
}

 
//recursive
void doReverse(ListNode* p, ListNode*& head){
  if(p->next == nullptr){
    head->next = p;
    return;
  }
  doReverse(p->next);
  ListNode* q = p->next;
  q->next = p;
  p->next = null;
}
ListNode* reverseList(ListNode* head){
  if(head == nullptr) return head;
  ListNode* dummy = new ListNode(INT_MIN);
  doReverse(head, dummy);
  return dummy->next;
}

LC92: Reverse linked list II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

1) first move (m-1) step to reach the node right before position m, denoted with 'head'
2) use two pointers 'pre' and 'cur' to reverse adjacent nodes, (n-m) times
3) now, 'cur' points to the node right after positions n, and 'pre' is one before
4) update the pointers

 
ListNode* reverseBetween(ListNode* head, int m, int n) {
  if(m<1 || m>=n || head==nullptr) return head;
  ListNode* dummy = new ListNode(INT_MIN);
  dummy->next = head;
  head = dummy;                           //avoid special handle when 'm=1'
        
  for(int i=0; i<m-1; ++i)
    head = head->next;
  ListNode* pre = head->next, *cur = pre->next;
  for(int i=0; i<n-m; ++i) {
    ListNode* next = cur->next;
    cur->next = pre;
    pre = cur;
    cur = next;
  }//--for
        
  head->next->next = cur;
  head->next = pre;
        
  head = dummy->next; delete dummy;
  return head;
}

LC24: Swap nodes in pairs

Given a linked list, swap every two adjacent nodes and return its head.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

 
ListNode* swapPairs(ListNode* head) {
  if(head==nullptr || head->next==nullptr) return head;
        
  ListNode* dummy = new ListNode(INT_MIN);
  dummy->next = head;
​
  int cnt = 0;
  ListNode* pre = dummy;
  ListNode *last=dummy, *cur = pre->next;
        
  while(pre->next!=nullptr && pre->next->next!=nullptr) {
    last = pre->next;
    cur = last->next;
            
    last->next = cur->next;
    cur->next = pre->next;
    pre->next = cur;
            
    pre = last;
  }//--while
        
  head = dummy->next;
  delete dummy;
  return head;
}

LC25: Reverse nodes in k-group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

dummy
 -----> [1 -> 2 -> 3] ->4 ->5
     pre               next
1) scan the list, find the 'pre' (one before the seg start) and 'next' (one after seg end)
2) reverse the nodes in between, and return the 'pre' for next seg (i.e, first of current seg)

 
//reverse nodes between 'pre' and 'next' (exclusive), e.g, -1 ->1->2->3 ->4
ListNode* revList(ListNode* pre, ListNode* next) {
  ListNode *last=pre->next, curr=last->next;
  while(curr != next) {
    ListNode* nt = curr->next;
    curr->next = last;
    last = curr;
    curr = nt;
  }//--while
  ListNode* rtn = pre->next;
  pre->next->next = curr;
  pre->next = last;
  return rtn;
}
ListNode* reverseKGroup(ListNode* head, int k){
  if(head==nullptr || k==1) return head;
  ListNode* dummy = new ListNode(INT_MIN);
  dummy->next = head;
  
  ListNode *pre=dummy, *cur=pre->next;
  int cnt = 0;
  while(cur != nullptr){
    ++ cnt;
    if(cnt % k == 0) {
      pre = revList(pre, cur->next);
      cur = pre->next;
    } else {
      cur = cur->next;
    }
  }//--while
  head = dummy->next;
  delete dummy;
  return head;
}

1.3 Arithmetic

LC2: Add two numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

 
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  ListNode* dummy = new ListNode(INT_MIN);
  ListNode* p = dummy;
  int carry = 0;
  while(l1!=nullptr || l2!=nullptr || carry) {
    int val1 = (l1==nullptr) ? 0 : l1->val;
    int val2 = (l2==nullptr) ? 0 : l2->val;
    int sum = val1 + val2 + carry;
    carry = sum / 10;
    p->next = new ListNode(sum%10);
    p = p->next;
    if(l1!=nullptr) l1 = l1->next;
    if(l2!=nullptr) l2 = l2->next;
  }
  return dummy.next;
}

LC445: Add two numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

 
//l1 is larger, l2 is shorter
ListNode* doAdd(ListNode* l1, ListNode* l2, int offset) {
  if(l1 == nullptr) return l1;
  ListNode* result = (offset==0) ? new ListNode(l1->val+l2->val) : new ListNode(l1->val);
  ListNode* post = (offset==0) ? new ListNode(l1->next, l2->next, 0) 
    : new ListNode(l1->next, l2, offset-1)
  if(post!=nullptr && post->val > 9) {
    post->val %= 10;
    result->val += 1;
  }
  result->next = post;
  return result;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  int len1 = getLength(l1); int len2 = getLength(l2);
       
  ListNode* dummy = new ListNode(1);
  if(len1>len2) {
    dummy->next = helper(l1, l2, len1-len2);
  } else {
    dummy->next = helper(l2, l1, len2-len1);
  }
  //handle psbl carry
  if(dummy->next->val > 9) {
    dummy->next->val %= 10;
    return dummy;
  }
  return dummy->next;
}

Similar: LC415: Add strings

LC369: Plus one linked list

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list.

 
ListNode* helper(ListNode* list) {
  if(list == nullptr) return list;
  ListNode* post = helper(list->next);
  if(post != nullptr && post->val>9) {
    post->val %= 10;
    list->val += 1;
  }
  if(post == nullptr){
    list->val += 1;
  }
  return list;
}

 
ListNode* plusOne(ListNode* head) {
  if(head == nullptr) return head;
  ListNode* dummy = new ListNode(0);
  dummy->next = head;
  head = dummy;
  ListNode* p1 = dummy;
  //find last non-9 node
  while(head != nullptr) {
    if(head->val != 9) p1 = head;
    head = head->next;
  }
  p1->val += 1;
  p1 = p1->next;
  while(p1 != nullptr) {
    p1->val = 0;
    p1 = p1->next;
  }
  return dummy->val==1 ? dummy : dummy->next;
}

Similar: LC66: Plus one

1.4 Fast/slow pointers

LC141: Linked list cycle

Given a linked list, determine if it has a cycle in it. O(1)

 
ListNode* slow = head;          //slow pointer
ListNode* fast = head;          //fast pointer
while(fast != nullptr && fast->next!=nullptr) {
  slow = slow->next;
  fast = fast->next->next;
  if(slow == fast) return true;
}//--while
return false;

LC142: Linked list cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. O(1)

L1: distance from 'head' to cycle 'entry'
L2: distance from 'entry' to first meeting point
C: cycle length
When the two pointers meet, L1 travel distance is 'L1+L2'
L2 travel distance is 'L1+L2+n*C', n is the times fast pointer travelled in the cycle
Faster is 2 times of slower, so we have
L1+L2+n*C = 2*(L1+L2) ==> L1=(n-1)C + (C-L2)
As '(n-1)C' just reaches the entry, we can see that
"ditance from head to entry equals to that of meeting point to entry"

 
ListNode *fast = head, *slow = head, *entry = head;
        
while(fast!=nullptr && fast->next!=nullptr) {
  slow = slow->next;
  fast = fast->next->next;
  if(fast == slow) {
    while(entry != slow) {
      slow = slow->next;
      entry = entry->next;
    }
    return entry;
  }
}//--while
return nullptr;

LC287: Find the duplicate number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. O(1) space, no more than $O(n^2)$ time complexity.

 
//binary search
int findDuplicate(vector<int>& nums) {
  int start=1, end=n;
  while(start <= end) {
    int mid = start + (end-start)/2;
    int cnt = 0;
    for(auto num : nums) {
      if(num <= mid) ++ cnt;
    }
    if(cnt > mid)               //there must be duplicate in first half
      end = mid - 1;
    else
      start = mid + 1;        //in second half
  }//--while
  return start<=n ? start : -1;
}

 
//find cycle entry
int findDuplicate(vector<int>& nums) {
  int slow=0, fast=0, find=0;
  do{
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow != fast);
  while(find != slow) {
    slow = nums[slow];
    find = nums[find];
  }
  return find;
}

Similar:

• LC268: Missing number
• LC136: Single number
• LC41: First missing positive
• LC448: Find all numbers disappeared in an array

LC19: Remove Nth node from end of list

Given a linked list, remove the nth node from the end of list and return its head.

 
ListNode* removeNthFromEnd(ListNode* head, int n) {
  ListNode *slow=head, *fast=head;
  for(int i=0; i<n; ++i) {
    fast = fast->next;
  }//--for
  if(fast == nullptr) {               //case: delete head
    head = head->next;
    return head;
  }
  while(fast != nullptr && fast->next != nullptr) {
    fast = fast->next;
    slow = slow->next;
  }//--while
  delete(slow->next);
  slow->next = slow->next->next;
  return head;
}

LC143: Reorder list

 
    void reorderList(ListNode* head) {
        if(head == nullptr) return;
        
        ListNode *p1 = head, *p2=head;
        //split list
        while(p2->next!=nullptr && p2->next->next!=nullptr) {
            p1 = p1->next;
            p2 = p2->next->next;
        }
        //reverse right half
        p1->next = reverseList(p1->next);
        //interleave
        ListNode* m1 = head;
        while(m1->next!=nullptr && m1->next->next!=nullptr){
            ListNode* next = m1->next;
            m1->next = p1->next;
            p1->next = m1->next->next;
            m1->next->next = next;
            m1 = next;
        }
    }

LC160: Intersection of two linked lists

Write a program to find the node at which the intersection of two singly linked lists begins.

LC234: Palindrome linked list

Given a singly linked list, determine if it is a palindrome.

Could you do it in O(n) time and O(1) space?

1.5 Sort

LC148: Sort list

Sort a linked list in O(n log n) time using constant space complexity.

 
//Merge sort
ListNode* sort(ListNode* head) {
  if(head==nullptr || head->next==nullptr) return head;
  
  ListNode* fast = head;
  ListNode* slow = head;
  while(fast->next!=nullptr && fast->next->next!=nullptr) {
    fast = fast->next->next;
    slow = slow->next;
  }//--while
  fast = slow;
  slow = slow->next;
  fast->next = nullptr;
  
  fast = sort(head);
  slow = sort(slow);
  
  return merge(fast, slow);
}
ListNode* merge(ListNode* l1, ListNode* l2) {
  ListNode* dummy = new ListNode(INT_MIN);
  ListNode *p=dummy, *p1=l1, *p2=l2;
  while(p1!=nullptr && p2!=nullptr) {
    if(p1->val < p2->val) {
      p->next = p1;
      p = p->next; p1 = p1->next;
    } else {
      p->next = p2;
      p = p->next; p2 = p2->next;
    }
  }//--while
  p->next = (p1==nullptr) ? p2 : p1;
  return dummy->next;
}
ListNode* sortList(ListNode* head) {
  
}

LC21: Merge two sorted lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

LC23: Merge k sorted lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

 
//merge each two
//O(1) space, O(nk^2) time: 2n+3n+...+kn
ListNode* mergeKLists(vector<ListNode*>& lists) {
  if(lists.size() == 0) return nullptr;
  ListNode* p = lists[0];
  for(int i=1; i<lists.size(); ++i) {
    p = merge2Lists(p, lists[i]);
  }//--for
  return p;
}

 
//min heap
//O(k) space, O(nklogk) time
//priority queue size is fixed at 'k', and insertion takes O(logk)
//in total, nk values should be inserted into the heap, and thus O(nklogk) time
ListNode* mergeKLists(vector<ListNode*>& lists) {
  if(lists.size() == 0) return nullptr;
        
  auto cmp = [](const ListNode* left, const ListNode* right) { return left->val>right->val; };
  priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
  for(auto list : lists) {
    if(list != nullptr) pq.push(list);
  }
  
  ListNode* dummy = new ListNode(INT_MIN);
  ListNode* tail = dummy;
        
  while(!pq.empty()) {
    tail->next = pq.top(); pq.pop();
    tail = tail->next;
    if(tail->next != nullptr) pq.push(tail->next);
  }//--while
  return dummy->next;
}

 
//binary search
//O(1) space, O(nklogk) time
ListNode *mergeKLists(vector<ListNode *> &lists) {
  if(lists.empty()) return NULL;
  int end = lists.size()-1;
  while(end>0) {
    int begin = 0;
    while(begin<end) {
      lists[begin] = merge2Lists(lists[begin], lists[end]);
      begin++; end--;
    }
  }
  return lists[0];
}
//see: http://bangbingsyb.blogspot.com/2014/11/leetcode-merge-k-sorted-lists.html

LC350: Intersection of two arrays II

Given two arrays, write a function to compute their intersection.

 
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int n1 = (int)nums1.size(), n2 = (int)nums2.size();
        int i1 = 0, i2 = 0;
        vector<int> res;
        while(i1 < n1 && i2 < n2){
            if(nums1[i1] == nums2[i2]) {
                res.push_back(nums1[i1]);
                i1++;
                i2++;
            }
            else if(nums1[i1] > nums2[i2]){
                i2++;
            }
            else{
                i1++;
            }
        }
        return res;
    }
};

LC147: Insertion sort list

Sort a linked list using insertion sort.

 
ListNode* findInsertPos(ListNode* list, int value) {
  ListNode *p=list, *pos=list;
  for(; p!=nullptr && p->val<=value; pos=p, p=p->next){}
  return pos;
}
ListNode* insertionSort(ListNode* head) {
  if(head == nullptr) return head;
  
  ListNode* dummy = new ListNode(INT_MIN);
  ListNode *p=head, *pnew=dummy;
  
  while(p != nullptr) {
    ListNode* pos = findInsertPos(pnew, p->val);
    ListNode* next = p->next;
    p->next = pos->next;
    pos->next = p;
    p = next;
  }//--while
  
  return dummy->next;
}

LC86: Partition list

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

 
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr) return head;
        
        ListNode* dummy1 = new ListNode(INT_MIN), *p1=dummy1;
        ListNode* dummy2 = new ListNode(INT_MIN), *p2=dummy2;
        
        while(head != nullptr) {
            if(head->val < x) {
                p1->next = head;
                p1 = p1->next;
            } else {
                p2->next = head;
                p2 = p2->next;
            }
            head = head->next;
        }//--while
        p1->next = dummy2->next; p2->next = nullptr;
        delete(dummy2);
        return dummy1->next;
    }

LC328: Odd even linked list

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

 
ListNode* oddEvenList(ListNode* head) {
        if(!head) return head;
        ListNode *odd=head, *evenhead=head->next, *even = evenhead;
        while(even && even->next) {
            odd->next = odd->next->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = evenhead;
        return head;
    }

LC61: Rotate list

Given a list, rotate the list to the right by k places, where k is non-negative.

 
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr) return head;
        ListNode* dummy = new ListNode(INT_MIN);
        dummy->next = head;
        int len = 1;
        while(head->next != nullptr) {
            ++ len;
            head = head->next;
        }//--while
        head->next = dummy->next;           //make a circle
        ListNode* p = dummy->next;
        for(int i=1; i<len-k%len; ++i) {    //k%n, instead of 'k'
            p = p->next;
        }//--for
        dummy->next = p->next;
        p->next = nullptr;
        return dummy->next;
    }

1.6 Others

LC379: Design phone directory

Design a Phone Directory which supports the following operations: get(), check() and release().

frequent remove/'get()' and add/'release()' operations

LC138: Copy list with random pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

2. List in C++ STL

2.1 forward_list

Forward lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence. forward_list is implemented as singly-linked list, keeping internally only a link to the next element.

front():		access first element
push_front():	insert element at beginning
pop_front():	delete first element
insert_after:	insert elements
erase_after:	erase elements

2.2 list

List containers are implemented as doubly-linked lists.

front():		access first element
back():			access last element
push_front():
pop_front():
push_back():
pop_back():
insert():		insert elements
erase():		erase elements

3. Heap/Priority Queue

 
template<
  class T,                          //type of the stored elements
  class Container = std::vector<T>,   //type of container to store the elements, vector/deque
  class Compare = std::less<typename Container::value_type> //provide a strict weak ordering
> class priority_queue;

A priority queue is a container adaptor that provides $O(1)$ time lookup of the largest (by default) element, at the expense of $log(N)$ insertion and extraction.

top(): 		access the top element
empty():	check whether the underlying container is empty
size():		return the #elements
push():		insert element and sort the underlying container
emplace():	construct element in-place and sort the underlying container
pop():		remove the top element
swap():		swap the contents

Examples:

 
priority_queue<int> q;
priority_queue<int, std::vector<int>, std::greater<int>> q2;
auto cmp = [](int left, int right) { return (left^1) < (right^1); }
priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);

4. Pointer/Dynamic Memory

A pointer variable is a variable that stores the address where another object resides. new() returns a pointer to the newly created object.

 
//NOT use 'new' when automatic variable can be used instead.
IntCell m(0);                   //a local variable, automatically reclaimed
IntCell *n = new IntCell(0);     //
delete n;

Dynamic memory managed through built-in pointers (rather than smart pointers) exists until it is explicitly freed. We can avoid memory leak issues by using smart pointers exclusively. The smart pointer will take care of deleting the memory only when there are no remaining smart pointers pointing to that memory.

 
void use_factory(T arg) {
  Foo *p = factory(arg);
  //use p but do not delete it
}//p goes out of scope, but the memory to which p points is not freed

 
//factory returns a shared_ptr pointing to a dynamically allocated object
shared_ptr<Foo> factory(T arg) {
  //process arg as appropriate
  //shared_ptr will take care of deleting this memory
  return make_shared<Foo>(arg);
}

Resetting the value of a pointer after a delete ...

when we delete a pointer, that pointer becomes invalid. Although the pointer is invalid, on may machines the pointer continus to hold the address of the (freed) dynamic memory. After the delete, the pointer becomes what is referred to as a dangling pointer. A dangling pointer is one that refers to memory that once held an object but no longer does so.

 
int *p(new int(42));        //p points to dynamic memory
auto q = p;                 //p and q point to the same memory
delete p;                   //invalidates both p and q
p = nullptr;                //indicates that p is no longer bound to an object
​
shared_ptr<int> p1 = new int(1024); //ERROR: must use direct init
shared_ptr<int> p2(new int(1024));  //OK: uses direct init