Han Zhu's Study Notes

Given a singly linked list  L :  L 0 → L 1 →…→ L n -1 → L n , reorder it to:  L 0 → L n → L 1 → L n -1 → L 2 → L n -2 →… You must do this in-place without altering the nodes' values. For example, Given  {1,2,3,4} , reorder it to  {1,4,2,3} . Thought process: The idea is to split the list into two halves, reverse the second half, and merge them back together. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public void reorderList ( ListNode head ) { if ( head == null ) { return ; } ListNode middle = findMiddle ( head ); ListN...

Sort a linked list in  O ( n  log  n ) time using constant space complexity. Thought process: In this case, merge sort does not take extra space because we are sorting a linked list. We can break the original list into pieces and merge them. Pay attention to the base case and the initialization of fast and slow pointers in findMiddle function. Make sure to eliminate all possibilities of infinite loop. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode sortList ( ListNode head ) { if ( head == null || head . next == null ) { return head ; } ListNode middle = findMiddle ( h...

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. For example, Given  1->4->3->2->5->2  and  x  = 3, return  1->2->2->4->3->5 . Thought process: The idea is to use two dummy nodes and two pointers. leftDummy.next is the sub-list where each node is less than x, and rightDummy.next is the sub-list where each node is greater than or equal to x. Link two lists together to get the partitioned list. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode partition ( Li...

Reverse a linked list from position  m  to  n . Do it in-place and in one-pass. For example: Given  1->2->3->4->5->NULL ,  m  = 2 and  n  = 4, return  1->4->3->2->5->NULL . Note: Given  m ,  n  satisfy the following condition: 1 ≤  m  ≤  n  ≤ length of list. Thought process: Say left = node before m and right = node after n, mNode = node at m and nNode = node at n. The idea is to find these four nodes, reverse the list between mNode and nNode based on "206. Reverse Linked List" , and connect left to nNode and mNode to right. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public L...

Reverse a singly linked list. click to show more hints. Hint: A linked list can be reversed either iteratively or recursively. Could you implement both? Thought process: Iterative: iterate through the linked list. Use a previous pointer that points to the node before the current node. Change current.next to previous. Recursive: use a helper function that passes in the previous node along with head. Base case: head == null, return previous. Otherwise: reverse list and proceed to next node. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode reverseList ( ListNode head ) { ListNode previous = null ; while ( head != null ) { ListNode next = head . next ; head . next = previ...

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty. Example: Given binary tree  1 / \ 2 3 / \ 4 5 Returns  [4, 5, 3], [2], [1] . Explanation: 1. Removing the leaves  [4, 5, 3]  would result in this tree: 1 / 2 2. Now removing the leaf  [2]  would result in this tree: 1 3. Now removing the leaf  [1]  would result in the empty tree: [] Returns  [4, 5, 3], [2], [1] . Thought process: The question asks us to "collect a tree's nodes as if you were doing this: collect and remove all leaves, repeat until the tree is empty". So we don't actually remove the leaves. Instead, we add a node to its correct list by calculating its height. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19...

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root. For example: Given a binary tree  {1,2,3,4,5} , 1 / \ 2 3 / \ 4 5 return the root of the binary tree  [4,5,2,#,#,3,1] . 4 / \ 5 2 / \ 3 1 confused what  "{1,#,2,3}"  means?  > read more on how binary tree is serialized on OJ. Thought process: After the flip, root and root.right will become siblings, and the left most child will become the new root. The idea is to traverse the tree to the left. As we traverse, we make root.left the new root, root.right the left child of new root, and root itself the right child of new root. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 /** * Definition for a binary ...

Given  s1 ,  s2 ,  s3 , find whether  s3  is formed by the interleaving of  s1  and  s2 . For example, Given: s1  =  "aabcc" , s2  =  "dbbca" , When  s3  =  "aadbbcbcac" , return true. When  s3  =  "aadbbbaccc" , return false. Thought process: Sub-problem: find whether s3[0, i + j] can be formed by the interleaving of s1[0, i] and s2[0, j]. Function:  If s3[i + j] comes from s1[i], then f[i][j] = f[i - 1][j]. If s3[i + j] comes from s2[j], then f[i][j] = f[i][j - 1]. Initialization: f[0][0] = true. f[i][0] = true if s1[0, i] equals s3[0, i]. f[0][j] = true if s2[0, j] equals s3[0, j]. Answer: f[s1.length][s2.length]. Check if s3.length == s1.length + s2.length before iterating through the matrix to prevent array index out of bound exception. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3...

Given a string  S  and a string  T , count the number of distinct subsequences of  T  in  S . A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,  "ACE"  is a subsequence of  "ABCDE"  while  "AEC"  is not). Here is an example: S  =  "rabbbit" ,  T  =  "rabbit" Return  3 . Thought process: Sub-problem: count the number of distinct subsequences of a substring of T and a substring of S. Function:  If the last character of S and T are not the same, the last character of S will not contribute to the subsequences. f[i][j] = f[i - 1][j]. Otherwise, we add the number of subsequences where the last character of S is in. f[i][j] = f[i - 1][j] + f[i - 1][j - 1]. Initialization:  If T is empty, there is one way to get ...