Linked List

Add Two Numbers Represented as Linked Lists
두 리스트의 길이를 계산한다.
길이가 같으면 recursion을 이용한다. 가장 오른쪽 노드에 도달할 때 까지 모든 노드를 recursion stack에 넣어 놓는다. 맨 오른쪽부터 합을 계산해서 carry를 왼쪽 노드로 전달한다.
길이가 다르면 긴 걸 차이만큼 오른쪽으로 이동해서 계산한다.


Merge Sort for Linked Lists
매 merge 작업마다 fast & slow runner를 이용해서 중간 지점을 찾는다.
그래서 앞 절반하고 뒤 절반으로 나눠서 recursive하게 작업한다.
base case는 길이가 0이나 1일 때로 한다.
그 다음에 나눠진 것들을 합치면서 recursion을 빠져나오는데 그때는 맨 처음 원소는 두 헤드 중 작은 원소를 넣고 그 다음 원소는 recursive하게 붙인다.
https://www.geeksforgeeks.org/merge-sort-for-linked-list/




Detect and Remove Loop in a Linked List
첫번째 방법:
fast & slow runner를 만들어서 만날 때 까지 탐색을 한다.
만나는 지점을 찾으면 그 곳을 기준으로 잡는다.
다시 리스트의 처음부터 보는데 각 노드마다 기준 노드에서 접근이 가능한지를 본다.
처음으로 기준 노드에서 접근이 가능해지는 곳이 사이클이 시작되는 곳이다.
두번째 방법:
위와 같이 일단 만나는 지점을 찾고 그때부터 하나는 헤드부터 하나는 만나는 지점부터 해서 한 칸씩 이동한다.
둘이 만나는 곳이 루프의 시작이다.
세번째 방법:
각 노드의 주소를 해시 맵에 저장해서 기존에 방문했었는지를 확인한다.




Select a Random Node from a Singly Linked List
첫번째 방법:
리스트를 돌면서 전체 길이를 알아낸다.
그중 랜덤하게 index를 뽑아서 그 리스트를 반환한다.
두번째 방법: 탐색을 한 번만 하는 방법
결과 노드를 선언하고 처음에는 헤드로 해놓는다.
두번째 노드를 볼 때 결과 노드가 두번째 노드로 1/2의 확률로 바뀌게 한다.
k번째 노드를 볼 때 결과 노드가 k번째 노드로 1/k의 확률로 바뀌게 한다.
그러면 마지막 노드는 1/n의 확률로 결과 노드가 되는 것이고, 마지막에서 두번째 노드는 (n-1)/n * 1/(n-1) = 1/n의 확률로 되니까 even하다.



-----------------------------------------------------
Reference
https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/#algo2