leetcode 206. Reverse Linked List

 

 

 

ListNode 를 뒤집을때 일단 첫번째로 생각해야하는것이 있다.

 

5 4 3 2 1 이 순서로 만들 생각을 하지말고

 

1 ->null

2 -> 1 -> null

3 -> 2 -> 1 -> null

 

이순서로 만들 생각을 해야된다.

 

첫번째 방법 - 재귀

 

재귀함수를 이용해보는 방법이다.

일단 함수호출하고 현재와 과거의 list를 보낸다고 생각해보자.

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
    
    public ListNode reverse(ListNode node, ListNode prev) {
    }
}

 

그리고나서 node.next = prev 를 붙일 생각을 해보자.

 

이때 node.next 는 별도장소에 보관하고있다가 다시 함수를 호출하기를 반복한다.

 

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
    
    public ListNode reverse(ListNode node, ListNode prev) {
        if (node == null) return prev;

        ListNode next = node.next;
        node.next = prev;
        return reverse(next, node);
    }
}

 

계속 돌아서 next가 없고 prev만 있다면 reverse가 완료된것이다.

 

요점은 next를 별도에 보관하고있다가 node.next 를 prev로 설정한것!

 

두번째방법 - 반복문

 

반복문도 비슷하게 흘러간다.

우선 현재 node 와 prev를 담을 변수를 생성해준다

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = head, prev = null;
    }
}

 

그리고 node.next를 별도로 저장하다가

node.next = prev 로 해주고

prev = 현재노드를 해준다.

 

node = next 노드이기때문에, node를 next 값으로 옮겨준다.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = head, prev = null;

        while(node != null) {
            ListNode next = node.next;
            node.next = prev; // node.next = null
            prev = node; // prev = [1, null]
            node = next; // node = [2,3,4]
        }
        return prev;
    }
}