[leetcode 75] 206. Reverse Linked List

문제해석

링크드리스트가 주어졌을 때 역순 변환해서으로 반환하기

 

정답 예

반복문으로 푸는 방법

public ListNode reverseList(ListNode head) {
    ListNode reverse = null;

    while (head != null) {
        // 새로운 head 생성
        ListNode tempHead = new ListNode(head.val);

        // 새로운 head의 다음 연결리스트를 기존 연걸리스트로 할당
        tempHead.next = reverse;

        // 새로운 head가 포함 된 연결리스트를 기존 리스트로 대체
        reverse = tempHead;

        // head의 다음 연결 리스트로 넘어감
        head = head.next;
    }

    return reverse;
}

 

재귀로 푸는 방법

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        return recursiveReverse(head, new ListNode(head.val));
    }

public ListNode recursiveReverse(ListNode head, ListNode reverse) {
    if (head == null || head.next == null) {
        return reverse;
    }

    // 새로운 head 생성
    ListNode temp = new ListNode(head.next.val);

    // 새로운 head를 기존 리스트의 다음으로 연결
    temp.next = reverse;

    // 기존 리스트를 새로운 리스트로 대체 후 호출 (head의 다음차순 포함)
    return recursiveReverse(head.next, temp);
}