[C언어]연결리스트 거꾸로 출력하기 (역순으로 만들기)

안녕하세요 주인장 H입니다. 오늘은 리스트를 거꾸로 만들어주는 코드를 알아보겠습니다. 

연결리스트(linked list를 잘 모르신다면) modernalchemist.tistory.com/39?category=921458

[C언어] 연결리스트 (linked list)

위의 글을 읽고 오시는 것을 추천드립니다.

일단 코드 먼저 보겠습니다. 

ListNode* reverse(ListNode* head)
{
	// 순회 포인터로 p, q, r을 사용
	ListNode* p, * q, * r;

	p = head;         		// p는 역순으로 만들 리스트
	q = NULL;         		// q는 역순으로 만들 노드
	while (p != NULL) {
		r = q;          	// r은 역순으로 된 리스트.    
					// r은 q, q는 p를 차례로 따라간다.
		q = p;
		p = p->link;
		q->link = r;      	// q의 링크 방향을 바꾼다.
	}
	return q;
}

 

이 코드만 보신다면 이해가 안가실텐데요 그림을 추가해보도록 하겠습니다.

기존에 노드를 가르키던 포인터를 왼쪽으로 몰아넣어 오른쪽으로 한 노드씩 쉬프트 시키면서 새롭게 link를 만들어주는 작업을 그림처럼 해주시면 됩니다.  이를 적용한 전체 예제를 보면 아래와 같습니다. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//
typedef int element;

//
typedef struct ListNode { 	// 노드 타입을 구조체로 정의한다.
	element data;
	struct ListNode* link;
} ListNode;

// 오류 처리 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

//
ListNode* insert_first(ListNode* head, element value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));//(1)
	p->data = value;//(2)
	p->link = head;	// 헤드 포인터의 값을 복사//(3)
	head = p;		// 헤드 포인터 변경//(4)
	return head;
}

//
void print_list(ListNode* head)
{
	for (ListNode* p = head; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}

//
ListNode* reverse(ListNode* head)
{
	// 순회 포인터로 p, q, r을 사용
	ListNode* p, * q, * r;

	p = head;         		// p는 역순으로 만들 리스트
	q = NULL;         		// q는 역순으로 만들 노드
	while (p != NULL) {
		r = q;        // r은 역순으로 된 리스트.    
			// r은 q, q는 p를 차례로 따라간다.
		q = p;
		p = p->link;
		q->link = r;      	// q의 링크 방향을 바꾼다.
	}
	return q;
}

// 테스트 프로그램
int main(void)
{
	ListNode* head = NULL;

	printf("> head list 생성.\n");
	head = insert_first(head, 10);
	print_list(head);
	head = insert_first(head, 20);
	print_list(head);
	head = insert_first(head, 30);
	print_list(head);

	printf("> After concat.\n");
	head = reverse(head);
	print_list(head);

	return 0;
}