.leetcode(206. Reverse Linked List)

https://leetcode.com/problems/reverse-linked-list/

 

//링크

 

3. 2022/05/02 시도

소요시간: 4분

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode current = head;
        ListNode newHead = head;
        while( current.next != null) {
            ListNode temp = newHead;
            newHead = current.next;
            current.next = current.next.next;
            newHead.next = temp;
        }
        
        return newHead;
    }
}

풀이 접근 과정

일단 edge케이스 예외처리를 한다.

노드들을 순회하면서 가장 앞으로 바꿔주면 되므로 항상 새로운 헤드(newHead)를 저장해두고
newHead 앞으로 이동시켜주는 로직을 만든다.

 

느낀점

• 여러번 풀어서인지 금방 풀 수 있었다.

---

 

2. 2022.01.01 시도

소요시간: 10분(4분 구상, 6분 코딩)

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode previous = null;       
        while(head.next != null) {
            ListNode temp = head.next;
            head.next = previous;
            previous = head;
            head = temp;
        }
        
        head.next = previous;
        
        return head;
    }
}

풀이 접근 과정

head의 예외처리는 잘 해줘야겠다.

리스트를 한번만 읽어서 풀 수 있겠다. 그리고 읽을 때 리스트 노드를 특정변수에 저장해두면 순서를 바꿔서 출력이 가능할 것이다.

 

느낀점

• 파스칼 삼각형 풀이 이후 시간복잡도가 최적인 풀이 방식이 보이면 바로 코딩하기로 마음먹었는데 이번에 그로인해 쓸데없이 고민하는 시간을 줄일 수 있엇다.
• 변수 두개를 이용하면 더 간단한 해법이 보인다.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode current = head;
        ListNode previous = null;       
        while(current != null) {
            ListNode temp = current.next;
            current.next = previous;
            previous = current;
            current = temp;
        }
        
        return previous;
    }
}

• 재귀함수를 이용할 수도 있다. 재귀함수를 이용할 때는 일단 메소드를 하나 만들고 접근해보는게 쉽다.
• 재귀는 기본적으로 iterative보다 공간을 더 쓴다. 이 경우도 O(n)의 공간 복잡도를 갖는다.

class Solution {
    ListNode ret = null;
    public ListNode reverseList(ListNode head) {
       if (head == null) {
           return head;
       }
        
        recursive(head); 
        return ret;
    }
    
    private ListNode recursive(ListNode current) {
        if (current.next == null) {
            ret = current;
            return current;
        }
        
        ListNode next = recursive(current.next);        
        next.next = current;
        current.next = null;
        
        return current;
    }
}

• 재귀함수도 더 간단하게 뽑아낼 수 있다. 여기서 핵심은 리턴해주어야할 바뀐 헤드를 계속해서 리턴으로 넘겨주고 실제 변형은 head.next.next를 이용한다는 점이다.

class Solution {
    public ListNode reverseList(ListNode head) {
       if (head == null || head.next == null) {
           return head;
       }
        
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

• 이전 시도와 비교해봤을 때, 고민의 길이가 짧아졌다. 확실하게 생각하고 코드도 간결해졌다.

 

 

1. 2021.01.02 시도

소요시간: 23분(recurstion), 16분(iterative)

# recursion
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode startNode = head;
        while(startNode.next != null) {
            startNode = startNode.next;

        }

        ListNode reversed = doReverseList(head);
        reversed.next = null;

        return startNode;
    }

    private ListNode doReverseList(ListNode head) {
        if (head.next == null) {
            return head;
        }

        ListNode reversed = doReverseList(head.next);
        reversed.next = head;

        return reversed.next;
    }
}

#iteratvie
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode startNode = head;
        ListNode prev = null;
        while(startNode != null) {
            ListNode temp = startNode.next;
            startNode.next = prev;
            prev = startNode;
            startNode = temp;

        }

        return prev;
    }
}

풀이 접근 과정

문제 자체에서 recursion과 iterative 두개를 풀어볼 것을 권유하고 있다. 이미 방법은 나온상태구나.
먼저 재귀로 푸려고 했다.

 

느낀점

1. 재귀로 풀때, 처음에는 잘 돌렸는데 시작지점(즉 답의 리턴값 시작점)을 잘못 제출했고 그 마지막 시점을 알고자하는게 하나있었고 또 뒤집은 리스트노드에서 마지막노드의 next를 null로 어떻게 업데이트할까가 고민이었다. 마지막을 알아야한다는 생각에 count를 세려고 했는데 그건 착오였다. 답의 시작점을 알기위해서 while을 사용햇고 기존 시작점의 next를 null로 업데이트하기 위해서는 메소드를 하나 생성해서 마지막에 업데이트치는 방식으로 해결했다.
2. ListNode에 대한 개념을 알아가는게 중요할 것이다.
3. 재귀는 이전과의 연결을 위해 prev변수를 썼는데 결과값 리턴의 시작점을 찾는게 헷갈려서 시간이 지연되었다.
4. 아 또 시간복잡도를 생각안해보았다. 꼭 해볼것.
5. ListNode는 그림을 그려서 확인해보는것도 좋을거같다. 솔루션을 보니 next next를 이용해 간단하게 문제를 정리하고 있었다.

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode reversed = reverseList(head.next); 
        head.next.next = head;
        head.next = null;

        return reversed;
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형