[자바 알고리즘 인터뷰] 8장 연결 리스트(3) - 역순 연결 리스트

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

 

- 연결 리스트를 뒤집어라 

 

 

풀이 1) 재귀 구조로 뒤집기 

 

- 다음 노드 next와 현재 노드 node를 파라미터로 하여 계속해서 재귀 호출

- node.next에는 이전 prev 리스트를 계속 연결해주면서 node가 널이 될 때까지 재귀호출하면 마지막에는 백트래킹되면서 연결 리스트가 거꾸로 연결된다. 

- 맨 처음에 리턴된 prev는 뒤집힌 연결 리스트의 첫 번째 노드가 된다. 

 

class Solution {
    public ListNode reverse(ListNode node , ListNode prev) {
        //현재 노드인 node가 널이면 리턴
        if(node == null)
            return prev;
        //현재 노드의 다음 노드 미리 지정
        ListNode next = node.next;
        //현재 노드의 다음으로 이전 노드 지정
        node.next = prev;
        //다음 노드와 현재 노드를 파라미터로 하여 재귀 호출
        return reverse(next,node);
    }

    public ListNode reverseList(ListNode head)
    {
        return reverse(head,null);
    }
}

 

 

풀이 2) 반복 구조로 뒤집기 

 

- 현재 노드의 다음 노드로 이전 prev 리스트를 계속 연결하면서 끝날 때까지 반복

- node가 널이 될 때 prev는 뒤집힌 연결 리스트의 첫 번째 노드가 된다. 

 

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

        //노드 끝으로 이동할 때까지 순회 
        while(node != null)
        {
            //현재 노드의 다음 노드 미리 지정
            ListNode next = node.next;
            //현재 노드의 다음으로 이전 노드 지정
            node.next = prev;
            //이전 노드는 현재 노드로 지정
            prev = node;
            //미리 지정했던 다음 노드를 현재 노드로 변경
            node = next;
        }

        //prev는 뒤집힌 연결 리스트의 첫 번째 노드 
        return prev;
    }
}