Linked List Summary


(1) How to judge whether there is a loop inside a linked list?
 Use quick and slow pointer.

(2) How to delete a node in a single linked list? Given node
Copy the next node to overwrite the given one.


Reference:
http://blog.csdn.net/fanoluo/article/details/49478079

Delete: 

237  Delete Node in a Linked List
        ListNode* next = node->next;
        // assert(next)
        node->val = next->val;
        node->next = next->next;

Reverse:

(1).   206  Reverse Linked List
     (a) Recursive
      Base cases: if (!head || !head->next) return head;
       Recursive formula:  recursive on the next element and get the newHead:
       ListNode *newHead = reverseList(head->next); Find the tail of the new reversed list.
       Set tail->next = head;  head->next = NULL;
    (b) Iterative:
     Keep 3 pointers, pre, cur, next. Initially, set pre to NULL, cur to head. while cur is not NULL,
     save the next element of cur to next pointer. set cur->next = pre, and set pre->next = NULL. Then
    move forward by setting pre = cur, cur = next. In the end return pre (which is the new reversed
    LinkedList head)


(2).





     Reverse the nodes between m and n are similar to 206. Except we have to save the element before
m (prev1) and the element after n (post2). So after reversing in between, we have to set prev1->next to new reversed node head if it is not NULL (otherwise, set head to the new head), and set post2 to the new tail.

Remove

(3). 83  Remove Duplicates from Sorted List
       (a)  Use hash set (unordered_set) to save the value that have encountered so far. If find duplicated remove, otherwise keep moving forward.
      (b)    Use three pointers: prev, current, runner. Outer loop while current is not null, inner loop while current is not equal runner. If runner->val == current->val remove and break inner loop. Otherwise,  move runner forward.  When exit inner loop (either break or not deletion at all). Check whether runner meets current or not, if so reset prev to current and current to its next.




82  Remove Duplicates from Sorted List II
(a)  Traverse the linked list once to use hash set (unordered_set) to save the value and its frequency. In the second loop, if a nodes have frequency larger than 1, remove all nodes that have such value in the linked list. Otherwise keep moving forward.














203 Remove Linked List Elements
  (a) Recursion: Base case: if (!head) return NULL. Recursion formula: head->next = removeElements(head->next, val),  return head->val == val ? head->next : head;
   (b) delete: keep 3 pointers ,  prev, cur and next. (case 1) When find the cur->val == val,   save it to tmp, set prev->next = cur->next,  cur =next (do not move prev in this case). (case 2) When not equal, move both prev and cur forward by one element, i.e : prev = cur, cur  = next;  Save the first non val node as the new node in the second case and return it as the new head.

 19 Remove Nth Node From End of List
        (step 1) Let q walk n step first.
        (step 2) Then both p and q walk forward at the same speed (one node
         each step) when q is NULL, p is the Nth element from the end

Merge

(1)  21  Merge Two Sorted Lists
       Create a helper ListNode and set head and tail to point to it. While l1 or l2 is not NULL, compare
the value of l1->val with l1->val. and set the smaller one to be the next of tail. Increase tail and the iterator of the LinkedList that has the smaller value.  Finally,  set head to be head->next, free the helper node and return head.

(2) Reorder List
      Using two pointers, one fast one slow to find the mid node of the linked list. Then the head of the second half is mid->next. Reverse the second half. And merge the first half and the reversed second half together to get the desired result.


Two pointers

141  Linked List Cycle
Idea: Using a fast pointer and a slow pointer. If there is a cycle, They will meet with each other. Otherwise, there is not cycle.


142  Linked List Cycle II
Suppose there are m nodes before the cycle (including the first one in the cycle)
and the cycle has n nodes, and fast and slow pointer meets at the (m + k) th node
in the cycle. The idea here is that at the meeting point, slow pointer has walked
(m + k) steps, since the faster walks twice as the slower pointer, it has walked
2 * (m + k) steps. Suppose fast pointer traveled N more time cycles before finally
encounter the slower pointer. Then we have 2 * (m + k) - N * n = m + k
i.e.: m + k = N * n. (N = 1, 2, ...). We transform this equation to the following
then it will be more clear. m = N * n - k. Which means if we pull the slow pointer
back to the beginning and leave fast pointer where it meets slow pointer.  And let
both pointer move forward by 1 node each time. When slow arrives at the m-th node.
faster will arrive at (m + k) + (N * n - k) = m +  N * n. i.e: faster walks another
N times of the cycle and arrives at node m, which is the first node in the cycle.

 234 Palindrome Linked List
 First use fast and slow pointer to find the middle of the linkedList. And
 then reverse the second half of the linkedList. Finally compare the first
 half and the second half to determine whether it is a palindrome.


328 Odd Even Linked List
Create three pointers : odd, even and evenHead to point to the odd nodes, even nodes and



even head. When even and even->next is not NULL, set odd->next = odd->next->next, and even->next = even->next->next. And move forward odd, even  by odd = odd->next, even = even->next.  Finally merge the the odd and even linked listed together by setting odd->next = evenHead. Return head.



61. Rotate List
O(N) time and O(1) space.
(1) caculate the length of the LinkedList
(2) If head is NULL or head->next is NULL or k % len is 0 return head
(3) Use two pointers front and rear to find the ne head after rotation.
    specifically, let both pointers point to the head initially. Let front
.    pointer move k steps first. Move both pointer forward by 1 each time
    until front->next is NULL.
 (4) let  front->next = head; (connect), head = rear->next (reset), rear->next = NULL (break)

24 Swap Nodes in Pairs
Recursion: Base case: if (!head || !head->next) return head
                  Recursion formula:
                 nextPair = head->next->next; 
                 newHead = head->next;
                  newHead->next  = head;
                  head->next = swapPairs(nextPair)
Non-Recursion:
       Similar with normal reversing, the only difference here is that we move two nodes forward each time and keep a tail pointer to link every two paris together.
In the loop:
     next = current->next;
     current->next = prev; // Swap within pair
     tail = prev;
     current = next ? next->next : NULL; // move forward two nodes
     prev = next;
     tail->next = current ? current :prev /* odd # nodes */;
    


 109      Convert Sorted List to Binary Search Tree
(a)  Convert to array and use the same solution in 108
(b)  If convert directly,  the only difference between construct tree from  array and from linked list, is the way to access the mid node.  For array we direct access using index arr[mid], while linked list need to start from head (index 0) and move forwad mid steps to access the mid node. Other than that, the code is similar with convert sorted array to binary search tree.

 19 Remove Nth Node From End of List 
        (step 1) Let q walk n step first.
        (step 2) Then both p and q walk forward at the same speed (one node
         each step) when q is NULL, p is the Nth element from the end

86  Partition List
Use two pointers leftTail and rightTail. Initialize them to two head nodes (to save its head, say leftHead, rightHead which are set to head initially). While the list is not NULL loop each node in the list, if head->val < x, add to left list and move left pointer to its next, otherwise add to right list, move right pointer to its next. For both cases move head to its next. Finally set leftTail->next = rightHead->next. rightTail->next = NULL, and return leftHead->next.

160Intersection of Two Linked Lists
 First calculate the length of both two Linked Lists, get the delta of the two length. Move the longer one forward by delta. And then in a loop judge if the two pointer have same value, if so we have found the intersection, return it. Otherwise move both linkedList forward by 1 node each time. If we hit the end of either of the two linked list and haven't  found intersection. That means there is no intersection at all.


Add Two Numbers

445 Add Two Numbers II
// Solution 1: reverse Linked List first and then add together
// Solution 2: Using two stack to add the two linked List in reverse order
// and create the sum linked list in reverse order (i.e: head insertion).

2Add Two Numbers
 Add the two numbers together with carry from beginning to end.

Sort List

147  Insertion Sort List

Loop each  nodes in the original linked list. Create a new node for each node inside the loop.  Keep going forward until find the element that has a larger value than current node value and insert the current node in front of it.

148  Sort List
        (s1) int len = getListLen(head);
        (s2)head = mergeSort(head, len);
              recursively call mergeSort to sort the first half and second half and then merge them together (divide and conquer), note the base case is (len == 0 or len == 1) it is NOT (!head || !head->next). And the while loop exit condition is (i < len1 || j < len2), it is NOT (head1 || head2)
        (s3)breakCircle(head, len);


Split

725Split Linked List in Parts
 Double while loop, the outer loop exit condition is p (initialized to head) not NULL. Inner loop exit condition is partLen decrease to zero. The hard part is how to calculate the partLen, it took me an hour to figure out the following formula:
int remainder = len % k;
 int partLen = res.size() < remainder ? (len / k) + 1 : (len / k);
Basically, you can think in this way. The best case is every part has length (len / k), if there are extra remainder length value, we want to distribute it as evenly as possible, so we add the 1 to the first remainder number of LinkedList part as requested.


Extended LinkedList

138 Copy List with Random Pointer

  Step1: Insert copy nodes
  Step2: copy the random pointer. q->random->random->next is the dst random pointer value for the new list.
  Step3: Recover the old list  using saved result in hash map































Comments

Post a Comment

Popular posts from this blog

zhitongguigu

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN
Read more

Array Part2

Two pointers 977 Squares of a Sorted Array      We can use two pointers to read the positive and negative parts of the array - one pointer  j  in the positive direction, and another  i  in the negative direction. Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique. 11 Container With Most Water      O(N) time and O(1) space, since better candidadates must use the taller line of l and r therefore we can use two pointer keep moving towards each other until they meet. Always abandon the shorter line while moving. 80 Remove Duplicates from Sorted Array II      tail = 0; for (int i = 0;  i < nums.size(); i++)           if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet                 nums[tail++] = nums...
Read more

Two pointers (Part 1)

344 Reverse String      Use two pointers i, j. keep switching elements at position i, j while i < j.     string reverseString(string s) {        for (int i = 0, j = s.size() - 1; i < j; i++, j--)            swap(s[i], s[j]);                  return s;     } 345 Reverse Vowels of a String      Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not. 283 Move Zeroes      Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero. 349 Intersection of Two Arrays      ...
Read more