########################################################### Nums so far: 15 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 2020.1.1 update: I realize since the most important thing in the interview is the process of thinking, I should write down and follow the thoughts when seeing a new question. starting today.//Copy the code#707. Design Linked List (Singly Linked List)
class ListNode{ int val; ListNode next; ListNode(int x) { val = x; } } class MyLinkedList { ListNode head; ListNode tail; int size; //int /** Initialize your data structure here. */ public MyLinkedList() { size = 0; } /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */ public int get(int index) { int value = -1; if(index > size - 1) return value; if(index == size - 1) return tail.val; if(index == 0) return head.val; ListNode cur = head; while(index >= 0){ if(index == 0){ value = cur.val; break; } index--; cur = cur.next; } return value; } /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */ public void addAtHead(int val) { if(head == null){ head = new ListNode(val); tail = head; } else{ ListNode node = new ListNode(val); node.next = head; head = node; } size++; } /** Append a node of value val to the last element of the linked list. */ public void addAtTail(int val) { if(tail == null){ tail = new ListNode(val); head = tail; } else{ tail.next = new ListNode(val); tail = tail.next; } size++; } /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */ public void addAtIndex(int index, int val) { if(index > size || index < 0) return; if(index == 0) addAtHead(val); else if(index == size) addAtTail(val); else{ ListNode cur = new ListNode(val), swim = head; while(index > 1){ swim = swim.next; index--; } cur.next = swim.next; swim.next = cur; size++; } } /** Delete the index-th node in the linked list, if the index is valid. */ public void deleteAtIndex(int index) { if(index > size - 1 || index < 0) return; if(index == 0) head = head.next; else if(index == size - 1){ ListNode node = head; while(node.next ! = tail) node = node.next; node.next = null; tail = node; } else{ ListNode swim = head; while(index > 1){ swim = swim.next; index--; } swim.next = swim.next.next; } size--; }}Copy the code#141. Linked List Cycle
public class Solution { public boolean hasCycle(ListNode head) { if(head == null || head.next == null) return false; ListNode slow = head, fast = head.next; while(fast.next ! = null && fast.next.next ! = null){ if(slow == fast) return true; slow = slow.next; fast = fast.next.next; } return false; }}Copy the code#142. Linked List Cycle II
public class Solution { public ListNode detectCycle(ListNode head) { if(head == null || head.next == null) return null; ListNode slow = head, fast = head; while(fast ! = null && fast.next ! = null && slow ! = null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ slow = head; while(slow ! = fast){ slow = slow.next; fast = fast.next; } return slow; } } return null; }}Copy the code#160. Intersection of Two Linked Lists
naive two hashmap solution, which is slow:
public class Solution { public ListNode getIntersectionNode(ListNode head_a, ListNode head_b) { Map<Integer, ListNode> hm1 = new HashMap<>(); while(head_a ! = null){ hm1.put(index_a++, iter_a); head_a = head_a.next; } while(iter_b ! = null){ hm2.put(index_b++, iter_b); iter_b = iter_b.next; } ListNode ans = null; while(index_a >= 0 && index_b >= 0 && hm1.get(index_a) == hm2.get(index_b)){ ans = hm1.get(index_a); index_a--; index_b--; } return ans; }}Copy the codethen one hashset, which is weird, slightly slower.
#19. Remove Nth Node From End of List
class Solution { public static ListNode removeNthFromEnd(ListNode head, int n) { ListNode slow = head, fast = head; for(int i = 0; i < n; i++){ fast = fast.next; } while(fast ! = null && fast.next ! = null){ slow = slow.next; fast = fast.next; } if(fast == null) return head.next; ListNode cur = slow.next.next; slow.next = cur; return head; }}Copy the code#206. Reverse Linked List //iterative
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode prev = null, cur = head;
while(cur != null){
ListNode tmp = cur.next;
cur.next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
}
Copy the code//recursive
class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode newhead = reverseList(head.next); head.next.next = head; head.next = null; return newhead; }}Copy the code#203. Remove Linked List Elements
class Solution { public ListNode removeElements(ListNode head, int val) { if(head == null || (head.val == val && head.next == null)) return null; while(head ! = null && head.val == val){ head = head.next; } if(head == null) return null; ListNode i = head, j = i.next; while(j ! = null){ if(j.val == val && j.next ! = null){ i.next = j.next; j = i.next; } else if(j.val == val && j.next == null){ i.next = null; break; } else{ i = i.next; j = j.next; } } return head; } } ListNode cur, prev; prev.next = cur; prev.next = null; // it works cur = null; //does not workCopy the code#328. Odd Even Linked List
class Solution{ public ListNode oddEvenList(ListNode head){ if(head == null) return head; ListNode odd = head, even = head.next, evenHead = even; while(even ! = null && even.next ! = null){ odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next; } odd.next = evenHead; return head; }}Copy the code#234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
- reverse the list and compare with the original, if two linked lists are the same then it is surely palindrome. time O(2n) space O(n)
- reverse second half of the linked list and compare two halves, time O(n), space O(1);
let’s focus on the implementation now:
-
reverse and compare all entire:
class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; ListNode dmyhead = new ListNode(-1), cur = head, cpy = dmyhead; while(cur ! = null){ ListNode curr = new ListNode(cur.val); cpy.next = curr; cpy = cpy.next; cur = cur.next; } ListNode i = reverse(dmyhead.next), j = head; while(i ! = null && j ! = null){ if(i.val ! = j.val) return false; i = i.next; j = j.next; } return true;
} public ListNode reverse(ListNode head){ if(head.next == null) return head; ListNode ans = reverse(head.next); head.next.next = head; head.next = null; return ans; }}
seems to be slow
-
reverse half and compare two halves: //much faster…
class Solution{ public boolean isPalindrome(ListNode head){ if(head == null || head.next == null) return true; ListNode i = head, j = head; while(j.next ! = null && j.next.next ! = null){ i = i.next; j = j.next.next; } j = (j.next == null) ? j : j.next; ListNode tail = reverse(i.next); //reverse second half while(head ! = null && tail ! = null){ if(head.val ! = tail.val) return false; head = head.next; tail = tail.next; } return true; } public ListNode reverse(ListNode head){ if(head.next == null) return head; ListNode ans = reverse(head.next); head.next.next = head; head.next = null; return ans; }}
#707. Design Linked List (Doubly Linked List)
class ListNode{
int val;
ListNode next, prev;
ListNode(int x) { val = x; }
}
class MyLinkedList {
ListNode head;
ListNode tail;
int size;
/** Initialize your data structure here. */
public MyLinkedList() {
size = 0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if(index + 1 > size) return -1;
ListNode cur = head;
int counter = 0;
while(counter < index){
cur = cur.next;
counter++;
}
return cur.val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
if(size == 0){
head = new ListNode(val);
tail = head;
}
else{
ListNode cur_head = new ListNode(val);
cur_head.prev = null;
cur_head.next = head;
head.prev = cur_head;
head = cur_head;
}
size++;
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
if(size == 0){
tail = new ListNode(val);
head = tail;
}
else{
ListNode cur_tail = new ListNode(val);
cur_tail.next = null;
cur_tail.prev = tail;
tail.next = cur_tail;
tail = cur_tail;
}
size++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
if(index > size) return;
if(index == size) addAtTail(val);
else if(index == 0) addAtHead(val);
else{
int counter = 0;
ListNode cur = head;
while(counter < index){
cur = cur.next;
counter++;
}
ListNode new_cur = new ListNode(val), prev_node = cur.prev;
new_cur.next = cur;
new_cur.prev = prev_node;
cur.prev = new_cur;
prev_node.next = new_cur;
size++;
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if(index + 1 > size) return;
if(index == 0) head = head.next;
else if(index + 1 == size) tail = tail.prev;
else{
int counter = 0;
ListNode cur = head;
while(counter < index){
cur = cur.next;
counter++;
}
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
size--;
}
}
Copy the code#21. Merge Two Sorted Lists
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2){ if(l1 == null || l2 == null) return l1 == null ? l2 : l1; ListNode ans = new ListNode(-1), cur = ans; while(l1 ! = null && l2 ! = null){ if(l1.val <= l2.val){ cur.next = l1; l1 = l1.next; } else{ cur.next = l2; l2 = l2.next; } cur = cur.next; } while(l1 ! = null){ cur.next = l1; l1 = l1.next; cur = cur.next; } while(l2 ! = null){ cur.next = l2; l2 = l2.next; cur = cur.next; } return ans.next; }}Copy the code#2. Add Two Numbers
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode ans = new ListNode(-1), p = ans;
while(l1 != null && l2 != null){
int cur = l1.val + l2.val + carry;
if(cur > 9){
carry = 1;
cur -= 10;
}
else carry = 0;
ListNode ans_cur = new ListNode(cur);
p.next = ans_cur;
p = p.next;
l1 = l1.next;
l2 = l2.next;
}
while(l1 != null){
int cur = l1.val + carry;
carry = cur > 9 ? 1 : 0;
cur = cur > 9 ? (cur - 10) : cur;
ListNode ans_cur = new ListNode(cur);
p.next = ans_cur;
p = p.next;
l1 = l1.next;
}
while(l2 != null){
int cur = l2.val + carry;
carry = cur > 9 ? 1 : 0;
cur = cur > 9 ? (cur - 10) : cur;
ListNode ans_cur = new ListNode(cur);
p.next = ans_cur;
p = p.next;
l2 = l2.next;
}
if(carry != 0){
ListNode extra = new ListNode(1);
p.next = extra;
}
return ans.next;
}
}
Copy the code#430. Flatten a Multilevel Doubly Linked List
1.head empty : output empty 2.depth first search
class Solution { public Node flatten(Node head) { if(head == null || (head.child == null && head.next == null)) return head; Node p = head; while(p ! = null){ if(p.child == null){ p = p.next; continue; } Node c = p.child; while(c.next ! = null) c = c.next; c.next = p.next; if(p.next ! = null) p.next.prev = c; p.next = p.child; p.child.prev = p; p.child = null; } return head; }}Copy the code#138. Copy List with Random Pointer
the goal of this question is to make “deep copy” of a linked list while each node of the list has a random slot pointing at another node in the list.
with hash map, mapping the original linkedlist to a newly built list of nodes, when update the .random and .next attributes, use hashmap to find the one in new linkedlist, so that avoid the relationship with the old one.
besides, the iteration method is new to me.
----- ----- | val | --> | val | ----- ----- | | | (next/random) | \ / \ / ----- ----- | val| --> | val | ----- ----- class Solution{ public Node copyRandomList(Node head){ Map<Node,Node> hm = new HashMap<>(); for(Node tmp = head; tmp ! = null; tmp = tmp.next){ hm.put(tmp, new Node(tmp.val)); } for(Node tmp = head; tmp ! = null; tmp = tmp.next){ hm.get(tmp).next = hm.get(tmp.next); //the .next node is the mapping of tmp.next instead of tmp.next itself hm.get(tmp).random = hm.get(tmp.random); } return hm.get(head); }}Copy the code#61. Rotate List
class Solution { public ListNode rotateRight(ListNode head, int k) { if(head == null || head.next == null || k == 0) return head; int len = 0; ListNode lentest = head; while(lentest ! = null){ len++; lentest = lentest.next; } if(k == len) return head; if(k > len) k %= len; if(k == 0) return head; ListNode i = head, j = head; for(int t = 0; t < k && j ! = null; t++) j = j.next; while(j.next ! = null){ i = i.next; j = j.next; } ListNode newhead = i.next; i.next = null; j.next = head; return newhead; }}Copy the code