LinkedList 과제 Fast, slow 포인터

Question

1. 현재 학습 진도 2챕터 과제, 끝에서 K번째 노드값 구하는 문제 LinkedList     2. 어려움을 겪는 부분 fast 포인터를 k만큼 움직이고 slow, fast를 동시에 움직여 fast노드가 끝에 도달때까지 반복해 k만큼 떨어진 slow노드를 반환하는것은 이해했습니다. 그런데 fast 노드를 끝까지 보내는 While 문 조건에서 저는 fast.next가 없을 때 가 마지막 노드라고 생각했습니다. 하지만 선생님이 실제로 구현할 때는 이전에 구두로 설명하신것과는 약간 다르게 fast 가 마지막 노드가 아닌 거기서 한번 더 반복되어 fast == None 일때까지 움직여 k번째 노드를 찾으시더라고요. 왜 마지막노드에서 멈추는게 아니라 설명과 좀 다르게 2개의 포인터를 한칸씩 더 움직여 none이 될때까지 움직이도록 했는지 궁금해 강의 끝 시각화 해주신 부분을 봤습니다. 강의 끝에 시각화 하는 부분에서도 첫번째 풀이방법의 답은 10, 두번째 풀이방법의 답은 9가 나오면서 각 풀이방법의 정답이 달라진것 처럼 나오게 됐습니다. 구두로 설명하셨던 것보다 결국 index를 한칸 더 가서 fast가 None이 돼야 정답이 되던데 일반적으로 LinkedList 문제에서 마지막 노드까지 반복문을 돌린다고 가정하면 원래 currentNode가 None이 될때까지 돌려서 푸는건가요???   이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. 김규태님, 질문 주셔서 감사합니다! 질문하신 LinkedList에서 fast, slow 포인터를 이용한 K번째 노드 찾기 문제에 대해 설명드리겠습니다. LinkedList에서 fast 포인터를 먼저 k 만큼 움직인 후에 slow 와 fast 를 함께 움직이면서 fast 가 None 에 도달했을 때 slow 가 가리키는 노드가 끝에서 K번째라는 것을 이해하셨군요. 여기서 fast 포인터가 None 이 될 때까지 반복문을 돌리는 이유를 설명드리겠습니다. 이는 마지막 노드를 포함하여 k 개의 노드를 앞서 보내기 위함입니다. fast 포인터를 k 만큼 먼저 전진시킵니다. 그런 다음, slow 와 fast 를 함께 이동시키되 fast 가 None 이 될 때까지 이동시킵니다. 이렇게 하는 이유는, fast 가 None 이 되면 slow 가 정확히 끝에서 k 번째 노드에 위치하게 되는 것과 같기 때문입니다. fast 가 끝 노드를 지나 None 에 도달해야만, slow 가 정확하게 k 번째 노드를 가리키게 됩니다. 이는 일반적으로 LinkedList와 같은 구조에서 빠르게 K번째 노드를 찾는 알고리즘입니다. 보통 LinkedList 문제에서는 currentNode 가 None 이 될 때까지 반복문을 돌리는 것이 관례입니다. 이는 명확하게 링크드 리스트의 끝을 확인하는 방법이기도 합니다. 김규태님의 질문은 좋은 이해를 돕기 위해 필요한 중요한 논점을 포함하고 있었습니다. 더 궁금하신 부분이 있으면 언제든지 질문해 주세요! 감사합니다. 😊 강의 관련하여 더 많은 정보가 필요하시면 여기를 방문해주세요: 인프런