[자료구조] 연결리스트(1) : 리스트를 역순으로 만드는 연산

✅ C언어로 쉽게 풀어 쓴 자료구조 : p.206-208 LAB

연결리스트를 역순으로 만드는 프로그램을 작성하여 보자. 이 함수에서는 세 개의 포인터 p,q,r 포인터를 사용하여 연결 리스트를 순회하면서 링크의 방향을 역순으로 바꾸면 된다. 새로운 연결 리스트를 만들지 않고 이와 같이 3개의 포인터를 사용하여 현재의 연결 리스트 안에서 문제를 해결하는 기법은 상당히 흥미롭다. 다만 주의할 점은 링크의 방향을 역순으로 바꾸기 전에 미리 뒤의 노드를 알아 놓아야 한다. p는 역순으로 만들 리스트이고 q는 현재 역순으로 만들 노드를 가리키며, r은 이미 역순으로 변경된 리스트를 가리킨다. r은 q, q는 p를 차례로 따라간다.

ListNode* reverse(ListNode *head)
{
  ListNode *p,*q,*r;
  p = head; 
  q= NULL;
  while(p!= NULL)
  {
    r = q;
    q = p;
    p = p -> link;
    q->link = r;
  }
  return q;
}