[leetcode #206] Reverse Linked List

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

・ The number of nodes in the list is the range [0, 5000].
・ -5000 <= Node.val <= 5000

Idea

그동안 leetcode를 안 풀었더니 뭔가 허전한 느낌이 들어 오늘부터 하루에 세 문제씩 밀린 문제를 풀어야겠다는 생각이 들었다. 다행히 어제・오늘은 아주 쉬운 문제인 것 같다.

List를 reverse하는 문제는 학부 때 들은 알고리즘 수업에도 나왔던 것 같다. 노드를 앞에서부터 탐색하면서 이전 노드와 다음 노드를 저장하고 현재 노드의 next 포인터를 이전 노드로 만든 뒤, 다음 노드를 현재 노드로 바꿔주면 된다. iteration이 끝난 뒤 이전 노드를 head 노드로 바꿔 리턴하면 된다.

알고리즘은 다음과 같다.

1. head가 null이면 곧바로 리턴한다
2. head 노드를 현재 노드, 이전 노드를 null, 다음 노드를 head 노드의 next 포인터로 설정한다.
3. 현재 노드가 null이 될 때까지 노드를 탐색한다.
   a. 다음 노드를 저장한다.
   b. 현재 노드의 next 포인터를 이전 노드로 설정한다.
   c. 이전 노드를 현재 노드로 변경한다.
   d. 현재 노드를 다음 노드로 설정한다.
4. head 노드를 이전 노드로 설정하고 head 노드를 리턴한다.

Solution

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

    	ListNode node = head;
    	ListNode prev = null;
    	ListNode next = node.next;

        while (node != null) {
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }

        head = prev;

        return head;
    }
}

Reference

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