1. 연결 리스트 란?
추상적 자료형인 리스트를 구현한 자료구조로, Linked List라는 말 그대로 어떤 데이터 덩어리(이하 노드Node)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다. 예를 들어 한 반에 있는 학생들의 자료를 저장한다면, 학생 하나하나의 신상명세 자료를 노드로 만들고, 1번 학생의 신상명세 자료에 2번 학생 신상명세가 어디있는지 표시를 해 놓는 방식이다. 쉽게 생각하면 자료를 비엔나 소시지마냥 줄줄이 엮어놓은 것이다.
2. 문제
3.풀이
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: result = [] if not head: return head node = head while node: result.append(node.val) node = node.next result = result[::-1] nodes = head while len(result) > 0: nodes.val = result.pop(0) nodes = nodes.next return head
첫번째 직접 풀이한 코드
이건 잘 모르는 상태여서 연결리스트를
배열로 가져온다음 슬라이싱 해서
다시 연결리스트로 추가해주는 방식으로 풀었습니다.
그러나 문제가 있다 시간복잡도가 좋지 못하다는 문제 점이다
그래서 배열을 사용하지 않고 풀어 보려 했으나 방식이 잘 떠오르질 않았다
해서 책에 나와있는 풀이법을 살펴 봤다.
4.책의 풀이
def reverseList2(self, head: Optional[ListNode]) -> Optional[ListNode]: def reverse(node:ListNode ,prev:ListNode =None) : if not node: return prev next ,node.next = node.next,prev return reverse(next,node) return reverse(head)
재귀 구조로 뒤집기 라는 방식이다
재귀함수를 사용해보지 않아서 사실 이해하는데 좀 시간이 걸렸다
해당 코드 를 풀이 해 보자면
핵심은
이부분이다. 나는 아직 저런방식이 눈에 잘 보이지 않아서
먼저 해당 코드를 보기 편한식으로 바꾸면 아래처럼된다.
next = node.next
node.next = prev
return reverse(next ,node)node값은 첫번째 재귀로 인해 reverse(head) 라는 부분에 의해
node = head 가 된다.
head = [1,2,3,4,5] 값이다
그럼 next = node.next
next = [2,3,4,5]
node.next = prev
node.next = None 이된다.
이렇게되면
node 값 [1,2,3,4,5] 에서
node.next 값인 [2,3,4,5] 가 None 이 되므로
node 에 남은 값은 [1] 이 된다.
리고 이떄 함수를 다시 재귀 해준다.
reverse(next , node)
이렇게 호출되면
다시 함수에 돌아왔을때 node값은 [2,3,4,5] 가 되고 prev값은 [1] 이 된다.
이후에 위와 같이
next = node.next
next = [3,4,5]
node.next = prev
node.next = [1] 이된다.
이렇게되면
node 값 [2,3,4,5] 에서
node.next 값인 [3,4,5] 가 [1] 이 되므로
node 에 남은 값은 [2,1] 이 된다.
해당방법으로 반복이 되면 결국 값은
[5,4,3,2,1] 로 역순으로 바뀌게 된다 .5. 느낀점
이번문제를 풀면서 연결리스트 라는 한번도 듣지못한 자료형에 대해 알게 됐다.
여태 배열에만 익숙해져서 배열로만 하는게 좋았는데 해당 자료형을 익숙하게 다루게 된다면
때에 따라선 유용하게 사용할수도 있을것 같다.
