[LeetCode]Reverse Linked List, JAVA 풀이

사용언어 : JAVA
난이도 :  Easy
문제 URL : https://leetcode.com/problems/reverse-linked-list/
참조 책 : 쓰면서 익히는 알고리즘과 자료구조(167~189page)

 

1.문제

-문제설명

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

singly linked list가 주어지면, 역순으로 뒤집어서 반환하라.

 

-제약사항

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

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: []

2.나의풀이

 1. 이전(prev), 현재(curr), 다음(next)를 유지 운영한다.
 2.현재 노드가 None(null)이 아닐때까지.
  - 현재(current)값을 임시 저장한다.

  - 현재 노드를 임시 저장한 다음 노드로 이동한다.

  - 현재(current)의 다음(next)를 이전(prev)를 가르키도록 업데이트 한다.

  - 이전(prev)를 현재 노드로 이동

 

그림으로 나타내면 아래와 같다.

 

 

 

head = 1일때,

-입력받은 head 값을 현재(current)값을 임시 저장한다.(current = head)

-입력받은 head값에 다음 노드의 값을 저장한다(head = head.next2)

-현재(current)의 다음(next)값을 이전(prev)를 가르키도록 업데이트 한다(current.next = prev)

    ※ prev 는 현재 null, 

- 이전(prev)을 현재 노드로 이동(prev = current) 

 

head = 2일때,

 

-head 값을 현재(current)값을 임시 저장한다.(current = head)

-head값에 다음 노드의 값을 저장한다(head = head.next2)

-현재(current)의 다음(next)값을 이전(prev)를 가르키도록 업데이트 한다(current.next = prev)

- 이전(prev)을 현재 노드로 이동(prev = current) 

 

이런식으로 노드가 끝날때까지 (head =null)  반복하게 되면 연결 리스트를 뒤집어서 반환 할 수있다.

 

 

 

3.코드구현(JAVA)

위의 풀이방법으로 코드를 구현하면 아래와 같다.

/**
 * 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) {
        
        ListNode prev = null;
        
        while ( head != null ){
            ListNode current = head;
            head = head.next;
            current.next = prev;
            prev = current;
        }
        
        
        return prev;
    }
}