刷题记录

Problem: Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Let's take the following BST as an example, it may help you understand the problem better: We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element. The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list. Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first...

Problem: Given a (singly) linked list with head node  root , write a function to split the linked list into  k  consecutive linked list "parts". The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null. The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later. Return a List of ListNode's representing the linked list parts that are formed. Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ] Example 1: Input: root = [1, 2, 3], k = 5 Output: [[1],[2],[3],[],[]] Explanation: The input and each element of the output are ListNodes, not arrays. For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null. The first element output[0] has output[0].val = 1, output[0].next = null....

Problem: Sort a linked list using insertion sort. A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list Algorithm of Insertion Sort: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 Analysis: It's easy if we remove node from original list and insert it to new list. Solution: class Solution { public ListNode insertionSortList ( ListNode head) { ListNode dummy = new Li...

Problem: Sort a linked list in  O ( n  log  n ) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 Analysis: Merge sort实现题。最底层递归返回条件是ListNode 只剩下一个了，就返回它自己。 findMid还是用fast 从head.next开始。 class Solution { public ListNode sortList ( ListNode head) { if (head == null || head . next == null) return head; ListNode mid = findMid(head); ListNode right = sortList(mid . next); mid . next = null; ListNode left = sortList(head); return merge(left, right); } private ListNode findMid ( ListNode head) { ListNode slow = head; ListNode fast = head . next; while (fast != null && fast . next != null) { slow = slow . next; fast = fast . next . next; } return slow; } ...

Problem: Given a singly linked list, determine if it is a palindrome. Analysis: Find mid and reverse mid them compare.  To get mid, how to find out whether fast starts from head or head.next. Suppose we have even list: 1-> 2 -> 3 -> 4 -> null  odd list: 1-> 2 -> 3 -> 4 -> 5 -> null From odd list, 3 is mid no matter fast starts from where. We want to reverse 3.next. Apply this conclusion to even list, reverse mid.next, so in even list mid has to be 2 instead of 3. We can decide fast starts from head.next now.  Solution: class Solution { public boolean isPalindrome ( ListNode head) { if (head == null) return true; ListNode slow = head, fast = head . next; while (fast != null && fast . next != null) { slow = slow . next; fast = fast . next . next; } ListNode mid = reverse(slow . next); while (mid != null) { ...

Problem: Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return  null . The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory. Analysis: Compare A's length and B's length. Trim the longer one to the length of the shorter one. Then start going afterward.  Solution: public class Solution { public ListNode getIntersectionNode ( ListNode headA, ListNode headB) { int lenA = len(headA); int lenB = len(headB); if (lenA < lenB) { ...

Problem: Given a non-negative integer represented as  non-empty  a singly linked list of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list. Example: Input: 1->2->3 Output: 1->2->4 Analysis: Two pointers. i reaches the last node before 9, j reaches the tail node. 1-> 2 -> 4 -> 9 -> null               i                 j We can set i.val++, and set node after i's val to 0. One corner case is the list starts with 9 and only has 9. like  9 -> 9->null. So we start checking 9 from dummy. Solution: class Solution { public ListNode plusOne ( ListNode head) { if (head == null) return null; ListNode dummy = new ListNode ( 0 ); dummy . next = head; ...

Problem: Given a linked list, remove the  n -th node from the end of list and return its head. Example: Given linked list: 1->2->3->4->5 , and n = 2 . After removing the second node from the end, the linked list becomes 1->2->3->5 . Note: Given  n  will always be valid. Analysis: 2 pointers. fast is n nodes away from slow.  Solution: class Solution { public ListNode removeNthFromEnd ( ListNode head, int n) { if (head == null) return null; ListNode dummy = new ListNode ( 0 ); dummy . next = head; ListNode slow = dummy, fast = dummy; for ( int i = 0 ; i < n; i ++ ) { fast = fast . next; } while (fast . next != null) { slow = slow . next; fast = fast . next; } slow . next = slow . next . next; return dummy . next; } }

Problem: Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only  distinct  numbers from the original list. For example, Given  1->2->3->3->4->4->5 , return  1->2->5 . Given  1->1->1->2->3 , return  2->3 . Analysis: Since it needs to remove all dup, so we need to have a pre pointer comparing to 82. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplicates ( ListNode head) { ListNode dummy = new ListNode ( 0 ); dummy . next = head; ListNode p = dummy; while (p . next != null && p . next . next != null) { if (p . next . val == p . next . next . val) { int dup = p . next . val; while (p . next != null && p ....

Problem: Given a sorted linked list, delete all duplicates such that each element appear only  once . For example, Given  1->1->2 , return  1->2 . Given  1->1->2->3->3 , return  1->2->3 . 05/01/2018 update: A better solution can be applied to II. public ListNode deleteDuplicates( ListNode head) { ListNode current = head; while (current != null && current . next != null) { if (current . next . val == current . val) { current . next = current . next . next; } else { current = current . next; } } return head; } Analysis: 看了II,这道题就非常简答了。 We can always move head to head.next. When encounters duplicate, use head.next = head.next.next. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode ...

Problem: 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. Example: Given  1->2->3->4->5->NULL , return  1->3->5->2->4->NULL . Note: The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on ... 05/02/2018 update: Convert the linkedlist to two linked lists above. There are two reasons to have this while condition. 1. when even.next == null, we reached the end. 2. odd.next points to even.next then odd goes one step further to odd.next. We have to make sure even.next is not null. Analysis: It's similar to copy randomlist. Just the last step split of copy random list. But have to be cautious about...

Problem: Given a linked list, swap every two adjacent nodes and return its head. For example, Given  1->2->3->4 , you should return the list as  2->1->4->3 . 5/1/2018 update: First.next is like next in regular reverse.  -------------------------------------------------------------------------------------------------------------------------------------------- Analysis: Simple reverse linked list, but need to think about how to handle head. dummy不是随便一初始化就行了，需要考虑dummy的安置问题，不留死角。 Solution: cur.next 把head给转移到了second, 然后cur就完成了任务，继续下一次reverse。 class Solution { public ListNode swapPairs ( ListNode head) { if (head == null) return null; ListNode dummy = new ListNode ( 0 ); dummy . next = head; ListNode prev = dummy; while (prev . next != null && prev . next . next != null) { ListNode first = prev . next, second = prev . next . next; firs...

Problem: 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. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807. 7/22/2018 update: It it different from merge two sorted list. This one uses || the other one uses &&. class Solution { public ListNode addTwoNumbers ( ListNode l1 , ListNode l2 ) { ListNode dummy = new ListNode ( 0 ) ; ListNode head = dummy ; int carry = 0 ; while ( l1 ! = null | | l2 ! = null | | carry = = 1 ) { int num1 = l1 = = null ? 0 : l1 . val ; int num2 = l2 = = null ? 0 : l2 . val ; int num = num1 + num2 + carry ; carry = num / 10...

Problem: Design and implement a data structure for  Least Recently Used (LRU) cache . It should support the following operations:  get  and  put . get(key)  - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value)  - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Follow up: Could you do both operations in  O(1)  time complexity? Example: LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4 4/11/2018 update: Use doubly linked list. Insert the most recently...

思路： 用当前节点next的值取代当前值。然后删掉node.next。一开始没想出来，这种题做一次就会了。

思路： 用merge sort的思想来做很简单，时间复杂度是O(nlogn)。因为没一次递归都要遍历链表找中点。 另一种是inorder traversal, 实在是太巧妙了，估计面试的时候想不出来。 实现： 关于找中点slow和fast初始化问题, fast =  head or fast  =  head.next对于最后结果并没有什么影响。

思路： Merge sort. 实现： 先排序mid.next, 在排序head。在排序head之前mid.next = null。 具体merge的时候，循环走完后检查left和right是否为空，如果不为空, 根据链表的特性，直接链接到temp上，不用再一个node一个node的加。

思路： 快慢指针，和找mid不同的是fast初始指向head.next。找到circle， head也开始往后走，当head == slow.next的时候head就是入口。

思路： 做法非常直观就不再赘述。难点是如何处理k。k>=0，情况就很多了。k会超过linked list的长度。k超过size倍数的部分就没有意义。直接对size取模就好了。k = k%size。

Problem: 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 may  not  modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it to 1->4->2->3. Example 2: Given 1->2->3->4->5, reorder it to 1->5->2->4->3. 05/02/2018 update: 这道题做完了，感觉linked list功力又上一层。把这一遍刷linked lsit总结的东西都用上了。所以在merge的时候想出来了最易读，效率最高点的方法。beat 100%。 Find mid和parlindrome list一样 fast 从head.next开始。mid.next = null是我自己想出来的。因为reverse过后，mid.next实际上还是指向之前的mid.next,要重构linked list必须把它指向null。 在merge的时候做法比较直接。head.next 指向secHead, secHead.next 指向 head.next, head.next和secHead.next会丢失，更新，所以需要先cache他们。 while条件只判断secHead != null就行了，因为secHead.length <= head.length。 class Solution { public void reorderList ( ListNode head) { if (head == null) return ; ListNode mid = findMid(head); ListNode ...