# 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
- 當題目要求是找到cycle, 想到two pointers: slow and faster
- 給你一條linked list, 要你找到cycle發生的那個點, 或是給你兩條linked list要你找到intersection, 最naive solution就是用一個dictionary, 把走過的node存到dictionary, 如果current node有在dictionary, bang!
- Given一條linked list, 判斷是不是palindrome

→ 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