위코드 코드카타 Week6 Day1 - Reverse Linked List

문제

singly linked list의 순서를 뒤집은 후 singly linked list의 헤드를 return 해주세요.

node는 다음과 같이 정의되어 있습니다.

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

1) singly linked list의 head를 인자로 받음.

2) 받은 singly linked list를 뒤집음.

3) 뒤집은 singly linked list의 head를 반환.

 

해결

- prev, current, next 포인터 생성

- prev은 current 전의 노드를, next는 current 다음 노드를 가리킴

- current는 head에서 시작

 

1) current 노드의 next 필드가 prev을 가리키게 함(앞 노드와 연결 끊고 뒷 노드와 연결시켜줌)

2) prev, current, next를 한 칸씩 앞으로 이동시킴

3) current가 None이 될 때까지 1, 2 반복 

4) 실행 중지되면 head가 prev을 가리키게 만듦

 

MyLinkedList에 reverse메서드를 구현하는 방식

GeeksforGeeks - Reverse a linked list 참고

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None 

class MyLinkedList:
    def __init__(self):
        self.head = None 
        self.size = 0

    def addAtIndex(self, index, val):
        if index > self.size:
            return -1 
        
        current = self.head 
        new_node = ListNode(val)

        if index <= 0:
            new_node.next = current 
            self.head = new_node 

        else:
            for _ in range(index - 1):
                current = current.next
            new_node.next = current.next 
            current.next = new_node 
        
        self.size += 1

    def get(self, index):
        if index < 0 or index >= self.size:
            return 
        
        current = self.head 
        for _ in range(index):
            current = current.next

        return current.val

    def deleteAtIndex(self, index):
        if index < 0 or index >= self.size:
            return
        current = self.head 
        for _ in range(index - 1):
            current = current.next 
        current.next = current.next.next

        self.size -= 1

    def addAtHead(self, val):
        self.addAtIndex(0, val)

    def addAtTail(self, val):
        self.addAtIndex(self.size, val) 
    
    def printList(self):
        temp = self.head 
        while(temp):
            print(temp.val)
            temp = temp.next

    def reverse(self):
        prev = None
        current = self.head
        while current:
            # next는 current 다음 위치로 한 칸 이동
            next = current.next
            # current의 next에 prev을 넣음 => reverse가 되는 시점
            current.next = prev 
            # prev를 current 위치로 한 칸 이동
            prev = current 
            # current는 next 위치로 한 칸 이동
            current = next
        # 마지막 노드에 prev이 위치하게 됨 => head로 설정
        self.head = prev


linkedList = MyLinkedList()
linkedList.addAtTail(100)
linkedList.addAtTail(200)
linkedList.addAtTail(300)
linkedList.printList()
# 100 200 300
linkedList.reverse()
linkedList.printList()
# 300 200 100