코테 스터디 29일차 TIL + 오늘의 학습 키워드 linkedList

- 오늘의 학습 키워드 LinkedList , 재귀, 반복
- 공부한 내용 본인의 언어로 정리하기

1. 재귀로 풀기 -오버플로우떴음 실패

-나머지 리스트를 뒤집음

-현재 노드를 처리해서 리스트의 마지막에 추가

-base case 리스트가 비었거나 한개의 노드만 있을때

 

수도코드

function reverseList(head):

  if head is null or head.next is null;
    return head
    
    //나머지 리스트를 뒤집어서 새로운 헤드를 만든다
    newHead = reverseList(head.next):
    
    //현재 노드를 리스트의 마지막에 추가한다.
    head.next.next=head
    head.next=null
    
    return newHead

1단계 재귀 호출 진행( 스택에 쌓임)

reverseList(1->2->3->4->5)
  reverseList(2->3->4->5)
    reverseList(3->4->5)
      reverseList(4->5)
        reverseList(5)
          - 여기서 기저 조건에 도달 (5.next == null)
          - 5를 그대로 반환

 

2단 재귀 호출이 반환되면서 연결 리스트 뒤집기

 

1) reverseList(5) 반환:

기저 조건에 도달하므로 그대로 5 반환
현재 리스트: 5

2) reverseList(4) 처리:

newHead = 5 (reverseList(5)의 반환값)
head = 4
head.next.next = head => 4.next.next = 4 => 5.next = 4
head.next = null => 4.next = null
현재 리스트: 5->4->null
반환: newHead (5)

3) reverseList(3) 처리:

newHead = 5 (여전히 전체 리스트의 새 헤드)
head = 3
head.next.next = head => 3.next.next = 3 => 4.next = 3
head.next = null => 3.next = null
현재 리스트: 5->4->3->null
반환: newHead (5)

4) reverseList(2) 처리:

newHead = 5
head = 2
head.next.next = head => 2.next.next = 2 => 3.next = 2
head.next = null => 2.next = null
현재 리스트: 5->4->3->2->null
반환: newHead (5)

5) reverseList(1) 처리 (최초 호출):

newHead = 5
head = 1
head.next.next = head => 1.next.next = 1 => 2.next = 1
head.next = null => 1.next = null
최종 리스트: 5->4->3->2->1->null
최종 반환: newHead (5)

 

head.next.next= head;

head.next=null 

 

1->2

head 는 1 

head.next 2

head.next.next= head는 2.next=1 이 되니까 2가 1을 가리킴

head.next=null은 1.next=null 1이 아무것도 안가르키게되고

2->1->null 이 된다는 뜻

 

ListNode nextNode = head.next;  // nextNode = 5
nextNode.next = head;           // 5.next = 4
head.next = null;               // 4.next = null

 

 

1 -> 2 -> 3 -> 4 -> 5 -> null  (원래 리스트)

// reverseList(5) 처리 (기저 조건)
5 -> null  (변화 없음)

// reverseList(4) 처리
4 -> 5 -> null  (처리 전)
5 -> 4 -> null  (처리 후: head.next.next = head; head.next = null;)

// reverseList(3) 처리
3 -> 4 -> 5 -> null  (처리 전, 하지만 실제로는 4의 next가 이미 변경됨)
5 -> 4 -> 3 -> null  (처리 후)

// reverseList(2) 처리
2 -> 3 -> 4 -> 5 -> null  (처리 전, 하지만 실제로는 연결이 이미 변경됨)
5 -> 4 -> 3 -> 2 -> null  (처리 후)

// reverseList(1) 처리
1 -> 2 -> 3 -> 4 -> 5 -> null  (처리 전, 하지만 실제로는 연결이 이미 변경됨)
5 -> 4 -> 3 -> 2 -> 1 -> null  (최종 결과)

 

 

---

2 . 반복법으로 풀기

 

세개의 포인터 prev, current, next 사용

리스트를 순회하면서 각 노드의 next 포인터 방향을 바꾼다.

시간 복잡도 O(n) 공간 복잡도 O(1)

 

수도코드

function reverseList(head):
    prev =null
    current = head
    
    while current is not null:
    	next = current.next //다음노드 저장
        current.next=prev //현재 노드의 포인터 뒤집기
        prev= current //prev 포인터 이동
        current=next  //current 포인터 이동
        
     return prev //새로운 헤드 이전의 마지막 노드

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

재귀로 푸는 방법 

head.next.next= head인것 진짜 이해 안감

  - 어떻게 해결했는지

현재 노드의 다음노드가 현재노드를 가리키게한다.

head.next  5

head.next.next 4 

(head.next  5). next 4

5.next = 4로 해석된다.

 

  - 무엇을 새롭게 알았는지

linkedlist인줄알았는데 재귀함수로 풀어야할수도 있구나

재귀함수 스택 오버플로우를 방지하기 위한 방법 재귀 깊이 제한을 해도 된다.

 

연결 리스트 문제 해결에 필요한 아이디어

1. 경계 조건에 주의한다. -빈 리스트, 단일 노드리스트 등의 특수 경우를 항상 고려할것

2. 포인터 주의: 연결을 끊기 전에 항상 필요한 참조를 저장해둘것

3. 다중 포인터 기법: 대부분의 연결리스트는 두개이상의 포인터를 사용하여 해결할수 있음

4. 시각화 : 각 단계에서 포인터가 어떻게 변화하는지 종이에 그려볼것

5. 재귀 vs 반복

 

  - 내일 학습할 것은 무엇인지