[알고리즘] Leetcode_206_Reverse_Linked_List

Problem

Solve

  public ListNode reverseList(ListNode head) {
        
        ListNode result = new ListNode();
        ListNode answer = result;
        Stack<Integer> stack = new Stack<>();
        while(head != null){
            stack.push(head.val);
            head = head.next;
        }

        while(!stack.isEmpty()){
            int val = stack.pop();
            ListNode temp = new ListNode();
            temp.val = val;
            result.next = temp;
            result = result.next;
        }

        return answer.next;
    }

1. stack 이용
   val 만 stack에 추가해서 새로운 ListNode 에 stack.pop()을 추가

public ListNode reverseList(ListNode head) {
	 ListNode newNode = null;
        
        while(head != null){
            ListNode next = head.next;
            head.next = newNode;
            newNode = head;
            head = next;
        }
        return newNode;
}

2. iterative
   while문 하나로 reverse 하는 것인데 많은 변수를 사용해야하는 것이 어려운 이유이다.

// 1 2 3 4 5
// next = head.next 2 3 4 5 | 3 4 5 | 4 5 | 5 | null
// head.next = newNode null | 1 null | 2 1 null | 3 2 1 null | 4 3 2 1 null
// newNode = head; 1 null | 2 1 null | 3 2 1 null | 4 3 2 1 null 5 4 3 2 1 null
// head = next; 2 3 4 5 | 3 4 5 | 4 5 | 5 | null

이해하면 쉬워보이는데 스스로 하려고 하면 참 어렵다. ㄱㅖ속 보자!