관리 메뉴

★조나단봉네 블로그★

[CS] 연결 리스트 뒤집기 (Reverse Linked List) 본문

[아는게 힘이다]/[프로그래밍]

[CS] 연결 리스트 뒤집기 (Reverse Linked List)

조나단봉 2010.02.28 15:45
테크니컬 면접 문제의 단골인 연결 리스트(Linked List). 그 중에서도 가장 많이 나온다는 뒤집기 문제이다. 

기본적인 연결 리스트를 구현 할 줄 알아야 겠다. C/C++을 이용한다고 할 때, struct 혹은 class로 먼저 node를 정의한다. 필요한 기본 함수로는 insert, delete, print(
traverse
traverse) 정도가 되겠다. delete는 뒤집기에는 필요하지 않으므로 생략한다. 

C/C++로 구현하기 위해서는 포인터에 대해서 알아야 한다. 새 노드를 head가 가리키는 첫 노드로 삽입하는 insert를 구현하기 위해서는 포인터의 포인터(A pointer that points to a pointer)를 인자로 넘겨야 head가 가리키는 노드를 새 노드로 변경할 수 있다는 점에 주의해야 한다. 

리스트를 뒤집는 reverse 함수를 구현할 때에도 잘못 생각하면 무한 루프에 빠지게 되는데 주의해야 한다. 이전 노드, 현재 노드, 다음 노드를 테이블로 그려보고 적절히 값이 어떻게 바뀌어야 할지 생각해보면 할 수 있다.

그런데, 종이만 주고 이걸 구현하라고 하면 쉽게 완성하지는 못할 것 같다. 포인터가 아직 완전히 익숙하지 않아서 부분부분 오류를 낼 것 같다. 조금 더 다양한 것을 구현해보는 연습을 해야겠다. 
6 Comments
  • 프로필사진 broYobi 2010.03.01 23:12 요즘 재미있는게 많이 포스팅 되네..ㅋ

    (쓸데없이)reverse를 recursion으로 만들고 싶지 않나?? ㅎㅎ
  • 프로필사진 Favicon of https://blog.sbnet21.com BlogIcon 조나단봉 2010.03.02 04:43 신고 recursion으로 만들자면, 구 연결 리스트에서 head 노드를 계속 떼어서 새로운 연결 리스트의 head 노드로 넣으면 되나? [NIL, 1->2->3->4], [1, 2->3->4], [1<-2, 3->4] 좀 이상하네. 어떻게 하면 되겠노?
  • 프로필사진 broYobi 2010.03.02 14:26 이건 어때?

    Node* reverse(Node *node){
    Node *newHead;
    if(node==NULL)
    return NULL;
    if(node->next == NULL)
    newHead=node;
    return node;
    }

    newHead = reverse(node->next);
    node->next->next = node;
    node->next = NULL;
    return newHead;
    }

    메인함수에서
    reverse(&head)를 head = reverse(head)로 바꾸고..
  • 프로필사진 Favicon of https://blog.sbnet21.com BlogIcon 조나단봉 2010.03.04 17:50 신고 {가 하나 빠진듯. if (node == NULL || node->next == NULL) return node;로 앞부분을 다 뭉뚱그려도 될 듯. 어쨌든, 잘 했네. recursive가 좀 더 직관적이긴 하네.
  • 프로필사진 서여빈 2011.07.19 10:43 우연히 보고서 한마디 적어봐요 ㅋ
    위의 방법도 있겠지만 이런 방법도 있겠네요~
    기존 연결리스트 A가 있고 다른 헤드 역할을하는 B라는 포인터가 있을때 A 연결리스트를 루프를 돌면서 선택되는 모든 노드를 무조건 B포인터의 다음 위치에 두는거죠. 그럼 B연결리스트는 A연결리스트의 역순으로 생성이 되고 마지막에 헤드값만 바꿔버리면 끝!
  • 프로필사진 Favicon of https://blog.sbnet21.com BlogIcon 조나단봉 2011.07.22 07:35 신고 결국 new linked list를 하나 만드는데 (with a new head - B)
    원래 list에서 순서대로 traverse하면서
    B에다 insert_after_headnode를 계속한다는 거군요.

    의견 감사합니다.
댓글쓰기 폼