2w | 28 LeetCode

2w | 28 LeetCode

LeetCode

1 3.5w | 47 LeetCode

2 3.5w | 47 LeetCode

1.

1

Linked List Node Head Node Tail Node

763 0x56432 0x56432

0x0 0 NULL

JavaScript val next

function ListNode(val) { this.val = val; this.next = null; }

next JavaScript

2

1

2 O(1) N N O(N)

O(N) O(1) N O(N)

3

1 Singly Linked List

2 Doubly Linked List

3 Circular Linked List

2.

Dummy Head N N+1

6

LeetCode 707 6 /code here/ 6

var MyLinkedList = function() { /* code here: */ }; MyLinkedList.prototype.addAtTail = function(val) { /* code here: val */ }; MyLinkedList.prototype.addAtHead = function(val) { /* code here: val */ }; MyLinkedList.prototype.get = function(index) { /* code here: index -1 */ //index 0 }; MyLinkedList.prototype.addAtIndex = function(index, val) { //code here: // index val //1. index //2. index //3. index 0 }; MyLinkedList.prototype.deleteAtIndex = function(index) { /* code here: index index */ };

1

new dummy tail

var listNode = function(val) { this.val = val this.next = null }; var MyLinkedList = function() { this.dummy = new listNode() this.tail = this.dummy this.length = 0 };

head tail null

  • head
  • tail

2

MyLinkedList.prototype.addAtTail = function(val) { // this.tail.next = new listNode(val) // tail this.tail = this.tail.next; // +1 this.length ++ };

tail tail.next tail

3

p p 3

  • p.next dummy.next
  • dummy.next p
  • tail dummy tail p

MyLinkedList.prototype.addAtHead = function(val) { // val const p = new listNode(val) // p.next p.next = this.dummy.next; //dummy.next this.dummy.next = p; // tail if (this.tail == this.dummy) { this.tail = p; } // +1 this.length ++ };

dummy

tail

4

index index 0 prev

  • prev.next prev.next null
  • prev target insert target

get getPrevNode

MyLinkedList.prototype.getPreNode = function(index) { if (index < 0 || index >= this.length) { return -1; } // front back let front = this.dummy.next let back = this.dummy // front back for (let i = 0; i < index && front != null; i++) { back = front; front = front.next; } // back prev return back };

2

  • target prev
  • prev dummy prev

getPrevNode get

MyLinkedList.prototype.get = function(index) { // index -1 //index 0 if (index < 0 || index >= this.length) { return -1; } // getPrevNode return this.getPreNode(index).next.val };

5

4

  • index
  • index
  • index 0

Case 1~3 Case 4 getPrevNode() Case 4

  • getPrevNode() index pre
  • pre

Case 1~4

MyLinkedList.prototype.addAtIndex = function(index, val) { if (index > this.length) { //Case 1. index return; } else if (index == this.length) { //Case 2. index this.addAtTail(val); } else if (index <= 0) { //Case 3. index 0 this.addAtHead(val); } else { //Case 4. // index pre const pre = this.getPreNode(index); // pre const p = new listNode(val); p.next = pre.next; pre.next = p; // +1 this.length++; } };

6

index 0 2

  • index
  • index

2 Case 1 Case 2 index getPrevNode

MyLinkedList.prototype.deleteAtIndex = function(index) { //Case 1. index if (index < 0 || index >= this.length) { return; } //Case 2. index //step 1. index const pre = this.getPreNode(index); //step 2. tail if (this.tail == pre.next) { this.tail = pre; } //step. 3 pre.next = pre.next.next; this.length--; };

7

/** * Initialize your data structure here. */ var listNode = function(val) { this.val = val this.next = null }; var MyLinkedList = function() { this.dummy = new listNode() this.tail = this.dummy this.length = 0 }; /** * Get the value of the index-th node in the linked list. If the index is invalid, return -1. * @param {number} index * @return {number} */ MyLinkedList.prototype.getPreNode = function(index) { if (index < 0 || index >= this.length) { return -1; } // front back let front = this.dummy.next let back = this.dummy // front back for (let i = 0; i < index && front != null; i++) { back = front; front = front.next; } // back prev return back }; MyLinkedList.prototype.get = function(index) { if (index < 0 || index >= this.length) { return -1; } return this.getPreNode(index).next.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. * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtHead = function(val) { // val const p = new listNode(val) // p.next p.next = this.dummy.next; //dummy.next this.dummy.next = p; // tail if (this.tail == this.dummy) { this.tail = p; } // +1 this.length ++ }; /** * Append a node of value val to the last element of the linked list. * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtTail = function(val) { // this.tail.next = new listNode(val) // tail this.tail = this.tail.next; // +1 this.length ++ }; /** * 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. * @param {number} index * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtIndex = function(index, val) { if (index > this.length) { //Case 1. index return; } else if (index == this.length) { //Case 2. index this.addAtTail(val); } else if (index <= 0) { //Case 3. index 0 this.addAtHead(val); } else { //Case 4. // index pre const pre = this.getPreNode(index); // pre const p = new listNode(val); p.next = pre.next; pre.next = p; // +1 this.length++; } }; /** * Delete the index-th node in the linked list, if the index is valid. * @param {number} index * @return {void} */ MyLinkedList.prototype.deleteAtIndex = function(index) { //Case 1. index if (index < 0 || index >= this.length) { return; } //Case 2. index //step 1. index const pre = this.getPreNode(index); //step 2. tail if (this.tail == pre.next) { this.tail = pre; } //step. 3 pre.next = pre.next.next; this.length--; }; /** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */

head

/** * Initialize your data structure here. */ var MyLinkedList = function() { this.head=null this.rear=null this.len=0 }; function ListNode(val) { this.val = val; this.next = null; } /** * Get the value of the index-th node in the linked list. If the index is invalid, return -1. * @param {number} index * @return {number} */ MyLinkedList.prototype.get = function(index) { if(index<0||index>this.len-1) return -1 var node=this.head while(index-->0){ if(node.next==null) return -1 node=node.next } return node.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. * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtHead = function(val) { var node=new ListNode(val) if(this.head==null) this.rear=node else node.next=this.head this.head=node this.len++ }; /** * Append a node of value val to the last element of the linked list. * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtTail = function(val) { var node=new ListNode(val) if(this.head==null) this.head=node else this.rear.next=node this.rear=node this.len++ }; /** * 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. * @param {number} index * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtIndex = function(index, val) { if(index<=0) return this.addAtHead(val) if(this.len<index) return if(index==this.len) return this.addAtTail(val) var node=this.head while(index-->1){ node=node.next } var newnode=new ListNode(val) newnode.next=node.next node.next=newnode this.len++ }; /** * Delete the index-th node in the linked list, if the index is valid. * @param {number} index * @return {void} */ MyLinkedList.prototype.deleteAtIndex = function(index) { if(index<0||index>this.len-1||this.len==0) return if(index==0){ this.head=this.head.next this.len-- return } var node=this.head var myindex=index while(index-->1){ node=node.next } if(myindex==(this.len-1)){ this.rear=node } node.next=node.next.next this.len-- }; /** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */

3.

1

pos 0 pos -1

1

head = [3,2,0,-4], pos = 1 true

2

head = [1,2], pos = 0 true

3

head = [1], pos = -1 false

O(1)

flag true

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { while(head){ if(head.flag){ return true }else{ head.flag = true head = head.next } } return false };

  • O(n) n
  • O(n) n

2 II

null

pos 0 pos -1

1

head = [3,2,0,-4], pos = 1 tail connects to node index 1

2

head = [1,2], pos = 0 tail connects to node index 0

3

head = [1], pos = -1 no cycle

flag flag head

O(n)

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var detectCycle = function(head) { while(head){ if(head.flag){ return head }else{ head.flag = true head = head.next } } return null };

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var detectCycle = function(head) { let fast = head let slow = head let cur = head while(fast && fast.next && fast.next.next){ slow = slow.next fast = fast.next.next if(fast == slow){ while(cur!=slow){ cur = cur.next slow = slow.next } return slow } } return null };

  • O(n) n
  • O(n) n

  • O(n) n slow O(N)+O(N)=O(N)
  • O(1) slow fast cur

3

c1

1

intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA= 2, skipB = 3 Reference of the node with value = 8 8 0 A [4,1,8,4,5] B [5,0,1,8,4,5] A 2 B 3

2

intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Reference of the node with value = 2 2 0 A [0,9,1,2,4] B [3,2,4] A 3 B 1

3

intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB= 2 null A [2,6,4] B [1,5] intersectVal 0 skipA skipB null

  • null.
  • O(n) O(1)

ab ba a b ab ba

  • pA pB
  • pA a b
  • pB b a
  • pA pB
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let pA = headA let pB = headB while(pA !== pB){ pA = pA === null ? headB : pA.next pB = pB === null ? headA : pB.next } return pA };

  • O(m + n) m n
  • O(1) A , B

4

head

1

[1,2,3,4,5] 3 ( [3,4,5]) 3 ( [3,4,5]) ListNode ans ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, ans.next.next.next = NULL.

2

[1,2,3,4,5,6] 4 ( [4,5,6]) 3 4

1
100

slow fast

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var middleNode = function(head) { let fast = head, slow = head while(fast && fast.next){ slow = slow.next fast = fast.next.next } return slow };

  • O(n) n
  • O(1)
    slow
    fast

5

1:

: 1->2 : false

2:

: 1->2->2->1 : true

O(n) O(1)

1 **

2

  • pointer head
  • null
  • true false

1

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var isPalindrome = function(head) { let a = "" let b = "" while(head){ const nodeVal = head.val a = a + nodeVal b = nodeVal + b head = head.next } return a === b };

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ let pointer function fn(head) { if(!head) return true const res = fn(head.next) && (pointer.val === head.val) pointer = pointer.next return res } var isPalindrome = function(head) { pointer = head return fn(head) };

  • O(n) n
  • O(1)

  • O(n) n
  • O(n) n n

6

head
G
G
G

1

: head: 0->1->2->3 G = [0, 1, 3] : 2 : ,0 1 G 2 [0, 1] G [3] 2

2

: head: 0->1->2->3->4 G = [0, 3, 1, 4] : 2 : 0 1 3 4 [0, 1] [3, 4] 2

  • N
    head
    1 <= N <= 10000
  • [0, N - 1]
  • 1 <= G.length <= 10000
  • G
    .

  • G +1

isComponent G isComponent false G isComponent false

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number[]} G * @return {number} */ var numComponents = function(head, G) { let cur = head let isComponent = false let res = 0 while(cur){ if(G.indexOf(cur.val) > -1){ if(!isComponent){ isComponent = true res++ } }else{ isComponent = false } cur = cur.next } return res };

  • O(m+n) O(m+n) m n G
  • O(1)

7 k

k 1 1

6 1 2 3 4 5 6 2 4

: 1->2->3->4->5, k = 2. 4->5.

slow fast

fast k k k k

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var getKthFromEnd = function(head, k) { let slow = head, fast = head; let cur = 0; while(cur < k){ fast = fast.next cur++ } while(fast){ fast = fast.next slow = slow.next } return slow };

  • O(n) n
  • O(n) n

4.

1

0 0

(2 -> 4 -> 3) + (5 -> 6 -> 4) 7 -> 0 -> 8 342 + 465 = 807

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { const l3 = new ListNode(0) // let p1 = l1 // let p2 = l2 let p3 = l3 // let carry = 0 // while(p1 || p2){ const v1 = p1 ? p1.val : 0 const v2 = p2 ? p2.val : 0 const val = v1 + v2 + carry // carry = Math.floor(val/10) // p3.next = new ListNode(val % 10) // if(p1) p1 = p1.next // if(p2) p2 = p2.next p3 = p3.next } // if(carry){ p3.next = new ListNode(carry) } return l3.next };

  • O(max(m, n)) m n
  • O(1)

2 II

0

(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 7 -> 8 -> 0 -> 7

push

  • stack1 stack2
  • dummyHead
  • 10 10 dummyHead
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { let stack1 = [], stack2 = []; while(l1){ stack1.push(l1) l1 = l1.next } while(l2){ stack2.push(l2) l2 = l2.next } let dummyHead = {next: null} let carry = 0 while(stack1.length || stack2.length){ let p1 = stack1.pop() let p2 = stack2.pop() let x = p1 ? p1.val : 0 let y = p2 ? p2.val : 0 let sum = x + y + carry let m = sum % 10 // let n = Math.floor(sum/10) dummyHead.next = { val: m, next: dummyHead.next} carry = n } if(carry){ dummyHead.next = { val: carry , next: dummyHead.next }; } return dummyHead.next };

  • O(max(m, n)) m n
  • O(m + n) m n

3

:

: 1->2->3->4->5->NULL : 5->4->3->2->1->NULL

head
head.next
,
head.next
head
head
head.next

:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { // let pre = null let cur = head // while (cur!= null){ // let next = cur.next // cur.next = pre // pre = cur cur = next } return pre };

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { // if(!head || !head.next){ return head } // let next = head.next // let result = reverseList(next) // head.next = null // next.next = head return result };

  • O(n) n
  • O(1)

  • O(n) n
  • O(n) n n

4 II

m n 1 m n

:

: 1->2->3->4->5->NULL, m = 2, n = 4 : 1->4->3->2->5->NULL

m n

m-1
n
n+1
m

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} m * @param {number} n * @return {ListNode} */ var reverseBetween = function(head, m, n) { // let dummy = new ListNode() dummy.next = head // m-1 let p = dummy for(let i =0; i<m-1; i++){ p= p.next } // m let pre = null let cur = p.next // m n for(let i = 0; i<= n-m; i++){ let next = cur.next cur.next = pre pre = cur cur = next } // p.next.next = cur p.next = pre return dummy.next };

  • O(n) n

  • O(1)

5

k k

1:

: 1->2->3->4->5->NULL, k = 2 : 4->5->1->2->3->NULL : 1 : 5->1->2->3->4->NULL 2 : 4->5->1->2->3->NULL

2:

: 0->1->2->NULL, k = 4 : 2->0->1->NULL : 1 : 2->0->1->NULL 2 : 1->2->0->NULL 3 : 0->1->2->NULL 4 : 2->0->1->NULL

  • k length-k
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var rotateRight = function(head, k) { if(!head || !head.next){ return head } // let tail = head let length = 1 while(tail.next){ length++ tail = tail.next } tail.next = head // k = k % length for(let i = 0; i < length - k; i++){ tail = tail.next } // head = tail.next tail.next = null return head };

  • O(n) n
  • O(1)

6 K

k k k

1->2->3->4->5 k = 2 : 2->1->4->3->5 k = 3 : 3->2->1->4->5

  • k
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var reverseKGroup = function(head, k) { let cur = head let count = 0 while(cur !== null && count !== k){ cur = cur.next count++ } if(count == k){ cur = reverseKGroup(cur, k) // while(count !== 0){ count-- let tmp = head.next head.next = cur cur = head head = tmp } head = cur } return head };

  • O(n) n
  • O(1)

7

1

head = [1,2,3,4] [2,1,4,3]

2

head = [] []

3

head = [1] [1]

  • [0, 100]
  • 0 <= Node.val <= 100

?

1

2 list temp list temp temp temp temp node1

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var swapPairs = function(head) { if(!head || !head.next){ return head } const newHead = head.next // head.next = swapPairs(newHead.next) // newHead.next = head // return newHead };

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var swapPairs = function(head) { if(!head || !head.next){ return head } const list = new ListNode(0) list.next = head let temp = list while(temp.next && temp.next.next){ const node1 = temp.next const node2 = temp.next.next //node1 node2 temp.next = node2 node1.next = node2.next node2.next = node1 // temp temp = node1 } return list.next };

  • O(n) n
  • O(n) n

  • O(n) n
  • O(1)

8

head
k

k
k
1

1

head = [1,2,3,4,5], k = 2 [1,4,3,2,5]

2

head = [7,9,6,6,7,8,3,0,9,5], k = 5 [7,9,6,6,8,7,3,0,9,5]

3

head = [1], k = 1 [1]

4

head = [1,2], k = 1 [2,1]

5

head = [1,2,3], k = 2 [1,2,3]

  • n
  • 1 <= k <= n <= 10
  • 0 <= Node.val <= 100

  • dummy head head
  • slow fast dummy cur k
  • cur k cur k k
  • k k
  • k cur k
  • head
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var swapNodes = function(head, k) { let dummy = new ListNode(0) dummy.next = head let i = 0, cur = dummy let slow = dummy, fast =dummy while(i++ < k){ fast = fast.next cur = cur.next } while(fast){ fast = fast.next slow = slow.next } let temp = cur.val cur.val = slow.val slow.val = temp return head };

  • O(n)
    n
  • O(1)

9

x x x

head = 1->4->3->2->5->2, x = 3 1->2->2->4->3->5

x x

mallHead largeHead next

large next next x small next largeHead next large smallHead next

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} x * @return {ListNode} */ var partition = function(head, x) { let small = new ListNode(0) const smallHead = small let large = new ListNode(0) const largeHead = large while(head){ if(head.val < x){ small.next = head small = small.next }else{ large.next = head large = large.next } head = head.next } large.next = null small.next = largeHead.next return smallHead.next };

  • : O(n) n
  • O(1)

10

root
,
k

: 1 null

k

1->2->3->4, k = 5//5 [ [1], [2], [3], [4], null ] ** 1

: root = [1, 2, 3], k = 5 : [[1],[2],[3],[],[]] : , root val= 1, root.next.val = 2,/root.next.next.val = 3, root.next.next.next = null output[0] output[0].val = 1, output[0].next = null output[4] null,

2

: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3 : [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]] : 1.

:

  • root
    [0, 1000]
    .
  • [0, 999]
    .
  • k
    [1, 50]
    .

length length/k length%k length%k

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} root * @param {number} k * @return {ListNode[]} */ var splitListToParts = function(root, k) { let cur = root let length = 0 while(cur){ cur = cur.next length++ } // let width = Math.floor(length/k), curry = length % k let num, temp let res = new Array(k); for(let i = 0; i < k; i++) { // num = i < curry ? width + 1 : width // num temp = cur = root; for(let j = 1; cur && j < num; j++) { cur = cur.next; } // root if(cur) { root = cur.next; cur.next = null; } else { root = null; } res[i] = temp; } return res };

  • O(N + k) N k
  • O(max(N, k))

11

L L0 L1 Ln-1 Ln L0 Ln L1 Ln-1 L2 Ln-2

1:

1->2->3->4, 1->4->2->3.

2:

1->2->3->4->5, 1->5->2->4->3.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {void} Do not return anything, modify head in-place instead. */ var reorderList = function(head) { if(!head || !head.next) return let slow = head let fast = head // while(fast && fast.next){ slow = slow.next fast = fast.next.next ? fast.next.next : null } // fast slow fast = slow.next slow.next = null slow = head // let pre = null let cur = fast while(cur){ let temp = cur.next cur.next = pre pre = cur cur = temp } // fast fast = pre // while(fast){ let slowNext = slow.next let fastNext = fast.next slow.next = fast fast.next = slowNext slow = slowNext fast = fastNext } };

  • O(n) n
  • O(1)

12

O(n log n)

1:

: 4->2->1->3 : 1->2->3->4

2:

: -1->5->3->4->0 : -1->0->3->4->5

1 O(n log n)

2

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var sortList = function(head) { // if(head === null || head.next === null){ return head } // let fast = head let slow = head while(slow.next && fast.next && fast.next.next){ slow = slow.next fast = fast.next.next } // const middle = slow.next slow.next = null // const left = head const right = middle return merge(sortList(left), sortList(right)) }; function merge (left, right) { // let res = new ListNode(null); // let prev = res; while (left && right) { // if (left.val < right.val) { [prev.next, left] = [left, left.next] }else { // [prev.next, right] = [right, right.next]; } // prev = prev.next; } // prev.next = left ? left : right; return res.next; }

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var sortList = function(head) { if(head === null || head.next === null){ return head } let cur = head let index = 0 const arr = [] // while(cur){ arr[index] = cur.val cur = cur.next index ++ } // arr.sort((a,b) => a-b) // cur = head index = 0 while(cur){ cur.val = arr[index] index ++ cur = cur.next } return head };

  • O(n) n
  • O(1)

  • O(n) n
  • O(n) n

13

head
val
Node.val == val

1

head = [1,2,6,3,4,5,6], val = 6 [1,2,3,4,5]

2

head = [], val = 1 []

3

head = [7,7,7,7], val = 7 []

  • [0, 10]
  • 1 <= Node.val <= 50
  • 0 <= k <= 50

dummyHead

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} val * @return {ListNode} */ var removeElements = function(head, val) { let dummyHead = new ListNode(0) dummyHead.next = head let pre = dummyHead, cur = head while(cur){ cur.val == val ? pre.next = cur.next : pre = cur cur = cur.next } return dummyHead.next };

  • O(n)
    n
  • O(1)

14

1:

: 1->1->2 : 1->2

2:

: 1->1->2->3->3 : 1->2->3

CURD

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function(head) { let cur = head while(cur && cur.next){ if(cur.val === cur.next.val){ cur.next = cur.next.next }else{ cur = cur.next } } return head };

  • O(n)
    n
  • O(1)

15 II

1:

: 1->2->3->3->4->4->5 : 1->2->5

2:

: 1->1->1->2->3 : 2->3

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function(head) { // 0 1 if(!head||!head.next){ return head } // let dummy = new ListNode() dummy.next = head // let cur = dummy while (cur.next &&cur.next.next){ if(cur.next.val === cur.next.next.val){ // let val =cur.next.val // while(cur.next &&cur.next.val === val) { cur.next = cur.next.next } }else{ cur = cur.next } } // return dummy.next };

  • O(n)
    n
  • O(1)

16 N

n

: 1->2->3->4->5, n = 2. 1->2->3->5.

n

N

  • N
  • N

N

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { // const dummy = new ListNode() dummy.next = head // let fast = dummy let slow = dummy // N while (n!==0){ fast = fast.next n-- } // while (fast.next){ fast = fast.next slow = slow.next } // N slow.next = slow.next.next return dummy.next };

  • O(n)
    n
  • O(1)

17

1->2->4, 1->3->4 1->1->2->3->4->4

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function(l1, l2) { // let head = new ListNode(); // let cur = head; while (l1&&l2){ if(l1.val<=l2.val){ // cur.next = l1 // l1 = l1.next }else{ cur.next = l2 l2 = l2.next } // cur = cur.next } // cur.next = l1!==null ? l1 : l2 // return head.next };

  • O(n + m) m n
  • O(1)

18 K

1

lists = [[1,4,5],[1,3,4],[2,6]] [1,1,2,3,4,4,5,6] [ 1->4->5, 1->3->4, 2->6 ] 1->1->2->3->4->4->5->6

2

lists = [] []

3

lists = [[]] []

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i]
  • lists[i].length
    10^4

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function(lists) { let len = lists.length if(!len){ return null } if(len === 1){ return lists[0] } // let res = mergeTwoKLists(lists[0], lists[1]) // lists.splice(0, 2, res) // return mergeKLists(lists) }; // function mergeTwoKLists(l1, l2){ let head = new ListNode(), pre = head while (l1 && l2) { if (l1.val > l2.val) { pre.next = l2 l2 = l2.next } else { pre.next = l1 l1 = l1.next } pre = pre.next } pre.next = l1 ? l1 : l2 return head.next }

  • O(NlogK) K N N/K O(N/K) K logK K K * logK K * logK * N/K O(NlogK)
  • O(1) K N O(1)

19

n
random

n
next
random

X
Y
X.random --> Y
x
y
x.random --> y

n
/
[val, random_index]

  • val
    Node.val
  • random_index
    0
    n-1
    null

head

1

head = [[7,null],[13,0],[11,4],[10,2],[1,0]] [[7,null],[13,0],[11,4],[10,2],[1,0]]

2

head = [[1,1],[2,1]] [[1,1],[2,1]]

3

head = [[3,null],[3,0],[3,null]] [[3,null],[3,0],[3,null]]

4

head = [] [] null

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.random
    null

1 1 2 1

2

  • 1 3 1 3 next
  • 3 2 3 2 next

i ( ) j i j next

3

/** *//Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; * }; */ /** * @param {Node} head * @return {Node} */ var copyRandomList = function(head) { if(!head){ return null } let p = head // while(p !== null){ let newNode = new Node(p.val) newNode.next = p.next p.next = newNode p = newNode.next } p = head // while(p !== null){ if(p.random){ p.next.random = p.random.next } p = p.next.next } let dummyHead = new Node(-1) p = head let cur = dummyHead // while(p !== null){ cur.next = p.next cur = cur.next p.next = cur.next p = p.next } return dummyHead.next };

  • O(n) n
  • O(n)

20

1

: 4->2->1->3 : 1->2->3->4

2

: -1->5->3->4->0 : -1->0->3->4->5

:

  1. dummyHead dummyHead.next = head head
  2. last last = head
  3. cur cur = head.next
  4. last cur
  • last.val <= cur.val cur last last curr last
  • cur pre cur cur
last.next = cur.next cur.next = pre.next pre.next = cur
  1. cur = last.next cur
  2. 5 6 cur
  3. dummyHead.next
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var insertionSortList = function(head) { if(!head){ return head } const dummyHead = new ListNode(0) dummyHead.next = head let last = head, cur = head.next while(cur){ if(last.val <= cur.val){ last = last.next }else{ let pre = dummyHead while(pre.next.val <= cur.val){ pre = pre.next } last.next = cur.next cur.next = pre.next pre.next = cur } cur = last.next } return dummyHead.next };

  • O(n) O(1) O(n) O(n) n
  • O(1)

21

O(1) O(nodes) nodes

1:

: 1->2->3->4->5->NULL : 1->3->5->2->4->NULL

2:

: 2->1->3->5->6->4->7->NULL : 2->3->6->7->1->5->4->NULL

:

a b

  • 0 1 2 head
  • a b node b
  • while a b a b
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var oddEvenList = function(head) { if(head === null || head.next === null || head.next.next === null){ return head } let a = head // let b = head.next // const node = head.next // b while(b !== null && b.next !== null){ a.next = b.next a = a.next b.next = a.next b = b.next } a.next = node return head };

  • O(n)
    n
  • O(1)