Leetcode-LinkedList

Note:

  • 當題目要求是remove nodes, 想到two pointes: prev and cur

→ type1: given a head of linked list and val, ask you to remove all nodes with this given val in the linked list

→type2: given a head of sorted linked list, ask you to remove all nodes with duplicate values

→type3: given a head of sorted linked list, ask you to remove nodes with duplicate values but keep one left.

  • 當題目要求是找到middle node, 想到two pointers: slow and faster

→ step1: find middle node

→step2:reversed the second half

→step3:compare the first half and second half, node by node

  • Given a linked list represent a binary number, to return associated integer

→ optimal solution 就是考你要知道binary representation

Given 一條linked list, 但不給你head, 而是給你一個node,要你刪除此node in O(1)

→ step0: 首先這個node to be deleted cannot be tail node

→ step1: 改變要刪掉node的val 用下一個node by node.val = node.next.val

→step2: remove下一個node by node.next = node.next.next

Given a singly linked list, 要你rotate k次

→step1: 先找到length和tail node
→step2: 把tail node和head node連接再一起

→step3: 找到new head的位置(把cur 移動length-k%length, 然後new_head = cur.next), 然後記得斷開linked list在最後

Implementation Notes:

  • Always 使用cur代表dummy node, 去移動

The below problems are related to Linked List

  • 203. Remove Linked List Elements

83. Remove Duplicates from Sorted List

  • 82. Remove Duplicates from Sorted List II
  • 876. Middle of the Linked List
  • 141. Linked List Cycle
  • 142. Linked List Cycle II
  • 160. Intersection of Two Linked Lists
  • 234. Palindrome Linked List
  • 237. Delete Node in a Linked List
  • 1290. Convert Binary Number in a Linked List to Integer
  • 445. Add Two Numbers II

I’m Taiwanese expat. I’v worked in Singapore as data scientist after graduation from Taiwan and currently I work in Amsterdam as machine learning engineer.