연결리스트를 시계방향으로 회전시키는 자바스크립트 프로그램

JavaScript의 연결 목록의 기본 구조는 JavaScript의 클래스를 사용하여 생성한 다음 노드를 한 위치에서 다른 위치로 이동하여 회전할 수 있습니다. 이번 글에서는 자바스크립트 프로그래밍 언어로 연결리스트를 시계방향으로 회전시키는 방법을 배워보겠습니다. 이러한 개념을 더 깊이 이해하기 위한 코드를 살펴보겠습니다.

주어진 문제에서는 연결 리스트가 주어졌고 이를 시계 방향으로 회전해야 합니다. 즉, 모든 이동에서 마지막 요소를 먼저 배치해야 하며, k번 회전해야 하는 경우 마지막 요소를 연결 목록의 헤드 또는 시작 노드 앞에 배치해야 합니다. 앞에서 본 연결 목록을 만들려면 데이터를 바인딩하는 클래스와 다음 요소에 대한 포인터가 필요합니다.

연결된 목록 구조

예

먼저 현재 노드의 값과 다음 노드에 대한 포인터를 저장할 클래스 노드를 만듭니다. 그런 다음 연결된 목록을 만드는 데 도움이 되는 푸시 기능을 만들고 마지막으로 연결 목록을 인쇄하는 데 도움이 되는 표시 기능을 만듭니다. 먼저 코드를 살펴보겠습니다 -

으아악

위 코드에서는 클래스 키워드를 사용하여 클래스를 생성하고 "this" 키워드를 사용하여 클래스 생성자에서 데이터와 다음 노드에 대한 포인터를 저장하는 섹션을 생성했습니다. p>

그 후, 두 개의 매개변수를 취하는 푸시 함수를 정의합니다. 첫 번째 매개변수는 연결 목록의 헤드이고 두 번째 매개변수는 연결 목록에 추가하려는 새 노드의 데이터입니다. 함수에서 새 노드를 생성하고 그 안에 값을 저장합니다. 헤드가 비어 있는지 확인한 다음(첫 번째 요소를 추가한다는 의미) 간단히 새 노드를 반환합니다. 그렇지 않으면 루프를 사용하여 연결된 목록의 끝으로 이동하여 거기에 새 노드를 추가합니다.

문제 해결

클래스를 생성하고 필요한 기본 함수를 정의한 후, 연결 목록의 회전을 나타내는 마지막 k 요소를 연결 목록의 앞으로 이동시키는 함수를 정의하는 주 함수로 이동합니다. 첫 번째 요소에 마지막 k 요소를 추가하는 방법에는 두 가지가 있습니다. 이는 연결된 목록의 오른쪽 회전과 동일합니다. 예: -

연결된 목록이 제공됩니다: 1 -> 2 -> 3 -> 4 -> 5 ->null

나열된 링크를 시계 방향으로 한 번 회전시키려고 하므로 다음과 같습니다 -

으아악

마찬가지로 연결 목록이 3번 회전하면 연결 목록은 다음과 같습니다. -

으아악

연결된 목록 앞에 마지막 요소를 추가하는 방법에는 하나씩 또는 한꺼번에 추가하는 두 가지 방법이 있습니다.

연결리스트를 하나씩 회전시켜 보세요

예

이 방법에서는 마지막 노드로 이동한 다음 이를 이전 헤드 노드로 이동하고 헤드 노드를 업데이트합니다. 먼저 코드를 살펴보겠습니다 -

으아악

위 코드에서는 위에서 정의한 기본 함수 연결 목록 코드를 사용하고 연결 목록을 회전하는 새로운 함수를 추가했습니다.

rotate 함수에서는 먼저 while 루프를 사용하여 연결 목록을 k번 순회하고 각 반복에서 연결 목록의 끝에서 두 번째 요소에 도달합니다. 그런 다음 연결 목록에서 연결 목록의 마지막 요소를 제거하고 연결 목록의 헤드 앞에 배치합니다. 마지막으로 새 헤더를 반환하고 display 함수를 사용하여 새 연결 목록을 표시합니다.

시간과 공간의 복잡성

연결리스트를 k번 이동시켰고 연결리스트의 크기는 N이므로 프로그램의 전체 시간복잡도는 O(N*K)입니다. 또한 추가 공간을 사용하지 않으므로 프로그램의 공간 복잡도는 상수인 O(1)입니다.

연결된 리스트를 한 번 회전

이전 코드에서는 요소를 하나씩 추가했는데 O(N*N) 시간이 걸렸기 때문에 연결 목록을 더 잘 이동하고 연결 목록의 크기를 얻을 수 있었습니다. 그 후 다시 연결된 목록을 순회하여 마지막 k개 요소를 가져와 연결 목록 앞에 추가하면 프로그램의 시간 복잡도가 O(1)이 됩니다.

결론

이 튜토리얼에서는 JavaScript 프로그래밍 언어로 연결 목록을 시계 방향으로 회전하는 방법을 배웠습니다. 개념을 심층적으로 이해하기 위해 코드를 살펴보았습니다. JavaScript의 연결 목록의 기본 구조는 JavaScript의 클래스를 사용하여 생성할 수 있으며 노드는 회전을 위해 한 위치에서 다른 위치로 이동할 수 있습니다. 프로그램의 시간 복잡도는 O(N*N)이며, 이는 O(N)으로 더욱 개선될 수 있는 반면, 프로그램의 공간 복잡도는 O(1)입니다.

위 내용은 연결리스트를 시계방향으로 회전시키는 자바스크립트 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!