Linked List (링크드리스트) 알고리즘_part 2

오늘은 링크드리스트 코드에 대해 공부해보자

 

#1 개념

링크드 리스트 Part 1. 에서 링크드리스트와 관련된 개념들을 설명하였고

리버스 링크드리스트에 대한 솔루션 1번 : 스택방식으로 링크드리스트 코드구현까지 해보았다. 

 

링크드 리스트 Part 1. 링크 :  https://jayindustry.tistory.com/11

Linked List(링크드리스트) 알고리즘_part 1.

 

 

이번엔 솔루션 2, 3의 방법으로 같은 문제를 풀어보자!

복습차원에서 링크드리스트 개념을 다시 가져와보았다.

 

 

< 링크드 리스트 >

 

- 리스트는 순서가 있는 데이터를 늘어놓은 형태의 자료구조, 각 원소는 노드라고 하며 각 노드는 데이터와 그 다음 노드를 가리키는 포인터를 갖고 있다.

- 링크드 리스트란 이 노드들을 연결시킨 자료구조

- 맨 앞과 맨 끝 노드를 각각 머리(HEAD), 꼬리(Tail)노드라고 부르며 노드의 앞쪽 노드를 ‘전임노드’, 뒤쪽 노드는 ‘후임노드’라고 부른다.

- 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가진다. 또한 각 포인터 변수의 주소도 따로 존재한다.

 

 

 

#2 예제코드 솔루션

아래 예제 코드를 분석하며 동작과정을 자세히 알아보자

 

문제)

# Given the 'head' of a singly linked list, reverse the list, and return the reversed list.

# 해석) head라는 링크드리스트가 주어졌을 때, 순서가 뒤집어진 리스트를 반환하라.

# Example 1:

# Input: head = [1,2,3,4,5]

# Output: [5,4,3,2,1]

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

 

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

 

 

 솔루션 2.  반복 알고리즘

 

설명 )

* p = prev , c = curr 두 개의 포인터를 만들어준다.

 

< 작동원리 >

1) 처음값

null  1->2->3->4->5->null 에서..

 

2) 결과물

null<-1<-2<-3<-4<-5    ->   1노드의 next를 null로 바꿔준다.

  p      c

 

3) 과정

null<-1   2->3->4->5->null

  p      c

 

->  노드 1의 넥스트포인터를(curr.next) null로 바꿔주고 p를 c포인터위치로, c를 다음노드위치로 바꿔준다.

->  위처럼 다음작업을 반복하기 위해 temp_next에 c의 초기 다음노드위치를 저장해놓은것이다.

 

4) 과정 반복

null<-1<-2   3->4->5->null

          p    c

 

 

* ListNode 클래스

- reverseList라는 함수는 ListNode라는 객체를 담고있는 배열을 입출력으로 사용해야하는 것을 나타낸다.

- self.val : 각 노드의 값, self.next : 각 노드의 다음노드의 레퍼런스를 담고있는 변수

 

* dummy 노드

- dummy -> null값으로 초기에 하나 만들어 사용한다.

- 역할 : head가 비어있어서 stack이 애초에 비어있는 null값일 경우가 있고 하나하나 pop하다보면 stack의 null값이 다음 루프의 node.next에 들어가면서 에러가 발생할 수 있다. 이런 까다로운 과정들을 dummy를 만들어주면서 자연스레 피해갈 수 있다.

- 마지막 return값에서 dummy.next -> 5이므로 stack을 거꾸로 했을 때의 인자를 반환하도록 한 것이다.

 

 

* 복잡도

 

0(n) : time 복잡도 : 링크드리스트 루프를 1번돌기 때문

 

0(1) : space 복잡도 : 2개 변수 외에는 추가메모리를 사용하지 않음

 

 

 

 

 솔루션 3.  재귀알고리즘

 

 

설명)

reverseList를 F함수라고 가정할 때,

head = [1,2,3,4,5]를 인자로 넘길때 아래처럼 호출이된다.

 

F(1->2->3->4->5->null) : 이 부분을 2부분으로 나눈다.

      F(2->3->4->5->null) -> 1 -> null : 노드 1에 대한 나머지는 서브링크드리스트이다.

             F(3->4->5->null) -> 2 -> null : 이렇게 재귀적으로 3,4,5를 인자로 넘긴다.

            ... 계속진행 ...

 

마지막 F(5->null)만 남을땐 인자로 넘어온 얘들을 결과로 호출한다. 그럼 아래처럼 역순으로 올라간다.

 

F(1->2->3->4->5->null) : 이 부분을 2부분으로 나눈다.

      F(2->3->4->5->null) -> 1 -> null : 노드 1에 대한 나머지는 서브링크드리스트이다.

             F(3->4->5->null) -> 2 -> null

                        5->4 ->null : 역순으로 위로 올라간다.

 

최종적단계에 다다르면 아래 형태가 모식도처럼 작동한다.

 

   <-----------

 1   5->4->3->2

  ->null

 

-> 1은 원래 2를 가리키는데 null을 가리키도록 바꾸고

-> 2는 원래 null을 가리키는데 1을 가리키도록 바꾼다.

이를 코드로 구현한 것이다.

 

 

 

->  필자의 알고리즘 코딩링크 참고하기 (깃허브)

https://github.com/seokjunHwang/Algorithm_Training

GitHub - seokjunHwang/Algorithm_Training: Daily Algorithm Training