Linked List는 각 노드에 두 개의 블록이 있는 선형 데이터 구조로, 한 블록에는 노드의 값 또는 데이터가 포함되고 다른 블록에는 다음 필드의 주소가 포함됩니다.
각 노드에 데이터와 연결 목록의 다음 노드를 가리키는 포인터가 포함된 연결 목록이 있다고 가정해 보겠습니다. 작업은 주어진 연결 목록을 분리하는 것입니다. 연결 목록을 분리한다는 것은 목록에서 홀수 인덱스 노드와 짝수 인덱스 노드를 분리해야 한다는 것을 의미합니다.
이 문제를 해결하기 위한 접근 방식
주어진 연결 목록을 분리하기 위해 홀수 인덱스, 짝수 인덱스 및 짝수 인덱스에 대한 값에 대해 각각 세 개의 포인터를 도입합니다. 그런 다음 전체 연결 목록을 반복하고 일부 값으로 포인터를 초기화합니다.
연결 목록에서 인덱싱은 '1'부터 시작하므로 특정 문자열에 대해 목록의 첫 번째 노드는 항상 홀수 인덱스 노드로 처리됩니다. 그러나 다음 노드는 짝수 인덱스 노드로 처리됩니다.
- 데이터가 있는 연결 목록을 가져오고 다음 노드에 대한 포인터를 가져옵니다.
- segregateList(listnode *head) 함수는 헤드 노드에 대한 포인터를 가져오고 분리된 연결 목록을 출력으로 반환합니다.
- 현재 목록의 선두를 가리키고 있는 3개의 포인터 oddIndex, evenIndex 및 evenHead를 초기화합니다.
- 전체 연결 목록을 반복하고 evenIndex의 다음 포인터로 oddIndex의 다음 포인터를 초기화합니다.
- 이제 전체 목록을 반복하고 evenIndex의 다음 포인터를 oddIndex의 다음 포인터로 초기화합니다.
- 머리 포인터를 반환합니다.
예시
#include <iostream>
using namespace std;
class node {
public:
int data;
node * next;
node(int d) {
data = d;
next = NULL;
}
};
node * segregateList(node * head) {
if (head == NULL) {
return NULL;
}
node * oddIndex = head;
node * evenIndex = head -> next;
node * evenHead = evenIndex;
while (evenIndex != NULL and evenIndex -> next != NULL) {
oddIndex -> next = evenIndex -> next;
oddIndex = oddIndex -> next;
evenIndex -> next = oddIndex -> next;
evenIndex = evenIndex -> next;
}
oddIndex -> next = evenHead;
return head;
}
void insertAtNode(node * & head, int data) {
node * n = new node(data);
n -> next = head;
head = n;
}
void print(node * head) {
while (head != NULL) {
cout << head -> data << "->";
head = head -> next;
}
}
int main() {
node * head = NULL;
// It could be possible that the head node contains NULL Value.
insertAtNode(head, 5);
insertAtNode(head, 8);
insertAtNode(head, 3);
insertAtNode(head, 1);
insertAtNode(head, 2);
print(head);
cout << endl;
segregateList(head);
print(head);
} 위의 코드를 실행하면 다음과 같이 출력이 생성됩니다.
출력
2->3->5->1->8->
주어진 연결 리스트는 2->1->3->8->5->입니다. 연결 리스트를 분리하면 2->3->5->1->8->과 같이 출력됩니다.