[leetcode] Reverse Linked List

문제

• 링크
• 단일 연결 리스트(singly linked list)의 head가 주어질 때, 거꾸로 뒤집는 문제다.
• 제약 조건
  • 노드 개수 범위: [0, 5000]
  • 노드 값 범위: -5000 <= Node.val <= 5000

풀이

1. stack 사용

풀기 전

• 거꾸로 뒤집는 거면 간단히 스택에 넣었다가 빼면 될 거라 생각했다.

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        Stack<ListNode> stack = new Stack<>();
        
        // 모든 노드를 스택에 넣는다.
        ListNode now = head;
        while (now.next != null) {
            stack.push(now);
            now = now.next;
        }

		// 스택에서 노드를 빼면서 연결시켜준다.
        ListNode newHead = now;
        while (!stack.isEmpty()) {
            now.next = stack.pop();
            now = now.next;
        }
        now.next = null;

        return newHead;
    }
}

푼 후

• 답은 잘 나왔는데 속도가 하위 5% 나왔다. 스택에 넣고 빼는 시간이 걸린 거 같다.

2. 투 포인터

풀기 전

• 다른 사람 코드 참고했다.
• 이전 노드, 현재 노드, 다음 노드를 가리키는 변수를 만들고, 한 칸씩 이동시키면서 연결 리스트를 뒤집는다. 좀 복잡할 수 있는데, 윈도우 사이즈가 3인 상태에서 옆으로 한 칸씩 이동한다고 상상하면 이해하기 쉽다.

코드

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev, cur, next;
        prev = null;
        cur = head;
        
        while (cur != null) {
            // 현재 노드에서 다음 노드를 가리킨다. 추후 현재 노드를 다음 노드로 옮기기 위해 사용한다.
            next = cur.next;
            
            // 현재 노드의 next를 반대로 돌려준다.
            cur.next = prev;
            
            // 이전 노드(prev)와 현재 노드(cur)를 한 칸씩 이동한다.
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

푼 후

• 사실 투 포인터가 아니라 쓰리 포인터가 아닐까.