beepbeep

문제 주어진 연결 리스트가 회문 구조인지 확인하는 문제이다. 살펴보기 문제를 보고 가장 먼저 생각난 방법은 리스트를 이용하는 방법이었다. 리스트를 만들어 노드값을 전부 저장한 후, 반복문을 이용해 리스트의 양끝에서부터 가운데로 순회하면서 양쪽의 값을 비교해 회문인지 확인하는 방법이다. 그래서 우선 리스트를 이용해 문제를 푼 다음, 206번 문제를 풀 때 배운대로 뒤집힌 연결 리스트를 만든 후 원본 연결 리스트랑 비교하는 방식으로 풀어보았다. 의도했던 대로 문제를 풀긴 했지만.. 더 좋은 풀이가 있는걸 알게 되어서 풀이를 참고해 한번 더 풀어보았다. 우선 두 개의 포인터를 이용해, 연결 리스트의 중간 지점을 찾아야 한다. 160번 문제에서 했던 것처럼 한 포인터(slow)는 한 번에 한칸씩만 이동하고, 다..

문제 주어진 연결 리스트를 역순으로 만드는 문제이다. 살펴보기 이 문제는 아주 유명하면서 중요한 문제라고 한다. 간단하게 후입선출법인 스택을 이용해 노드를 저장했다가 다시 꺼내는 방식으로 뒤집을 수 있지만, 이 방법보다는 포인터를 이용해 노드를 뒤집는 방법이 더 적절하다고 한다. 포인터를 이용한 방법에서는 총 3개의 준비물이 필요하다. 주어진 노드, 노드를 순회할 포인터, 역순을 저장할 노드 주어진 노드 head와, head의 현재 노드를 가리킬 temp, 뒤집을 노드를 저장할 노드 reverse를 이용해서 문제를 풀었다. ListNode인 temp를 생성해 head를 가리킨다. head는 다음 칸으로 한 칸 이동시킨다. temp의 다음 노드를 reverse와 연결한다. 마지막으로 reverse를 tem..

문제 주어진 두 연결 리스트가 교차하고 있는지 확인해서 교차점이 있으면 해당 교차점의 노드를, 없으면 null을 반환하는 문제이다. 살펴보기 두 가지 방법을 이용해서 풀어보았다. 첫 번째 방법은 두 연결 리스트의 현재 노드부터 교차점까지의 거리를 일치시킨 후, 두 연결 리스트를 동시에 순회하면서 노드의 주소값을 비교하는 방법이다. 예를 들어 주어진 두 연결리스트가 아래와 같은 모습을 띈다면 빨간색 네모를 친 2칸만큼 파랑색 연결 리스트가 더 길다. 만약 두 연결 리스트를 동시에 순회할 경우, 노랑색 연결 리스트가 파랑색 연결 리스트보다 2칸 앞서가게 돼서, 두 노드의 교차점을 찾을 수 없다.. 그래서 두 연결 리스트의 길이 차이인 2만큼 파랑색 연결 리스트를 이동한 후 두 연결 리스트를 동시에 순회하면 ..

문제 주어진 연결 리스트가 순환하고 있는지 확인하는 문제이다. 살펴보기 문제를 푸는 방법은 여러 가지가 있다고 하는데 2개의 포인터를 이용하는 방법(투 포인터 알고리즘)이 가장 자주 쓰이는 것 같고, 컬렉션을 이용하는 방법도 많이 쓰이는 것 같다. 먼저 포인터를 이용하는 방법은 head와 연결된 두 노드를 활용한다. 한 노드는 한 칸씩(.next), 다른 노드는 한번에 두 칸씩(.next.next) 이동시킨다. 리스트가 순환하고 있다면, 두 노드가 순회하다가 만나게 된다! 그러나 순환하고 있지 않다면 null을 만나서 순회가 끝나게 된다. 컬렉션을 이용하는 방법은 간단하다. 컬렉션을 하나 만들고, 컬렉션에 방문한 노드의 주소값을 저장해둔다. 그리고 노드를 방문할 때마다 컬렉션에 해당 노드의 주소값과 동일..