leetcode 206(Reverse Linked List) - Java

SMJ·2023년 7월 25일
0

leetcode

목록 보기
3/7

문제

singly linked list가 주어지면 목록을 뒤집고 reversed list을 반환합니다.

예1

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

예2

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

예3

Input: head = []
Output: []

제약 조건

list의 노드의 수의 범위는 [0, 5000]이다.
-5000 <= Node.val <= 5000

코드

/**
 * 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 reverse = null; 
        ListNode pre = null; 
        ListNode curr = head; 

        if(head == null) return null;

        while(curr != null) {
            pre = reverse;      
            reverse = curr;     
            curr = curr.next;   
            reverse.next = pre; 
        }
        return reverse;
    }
}

풀이

class Solution {
   public ListNode reverseList(ListNode head) {
       ListNode reverse = null; 
       ListNode pre = null; 
       ListNode curr = head; 

       if(head == null) return null;
  • 새로운 노드 reverse를 생성한다. (reverse 연결리스트 만들기위함)
  • 새로운 노드 pre를 생성한다. (이전 노드를 가리키기 위함)
  • cuur로 보기 이해를 더 쉽게하기 위해 head를 curr에 할당한다.
  • 만약 매개변수로 주어지는 head가 비었으면 null을 리턴한다.
while(curr != null) {
            pre = reverse;      
            reverse = curr;     
            curr = curr.next;   
            reverse.next = pre; 
        }
        return reverse;
    }
}

pre를 reverse의 현재 노드를 넣는다. (할당한다)
reverse 노드에 curr 노드를 넣는다. (할당)
curr 노드를 다음 curr 노드로 수정한다. (할당)
reverse 노드가 pre 노드(이전노드)를 가리킨다.

Input: head = [1,2,3,4,5] 
1.
pre = null;
reverse = 1;
curr = 2;
reverse.next = null;  //reverse : 1 (->null)

2.
pre = 1;
reverse = 2;
curr = 3;
reverse.next = 1;  // reverse : 2->1 (->null)

3.
pre = 2;
reverse = 3;
curr = 4;
reverse.next = 2;  // reverse 3->2->1 (->null)

4.
pre = 3;
reverse = 4;
curr = 5;
reverse.next = 3;  // reverse 4->3->2->1 (->null)

5.
pre = 4;
reverse = 5;
curr = null //반복문 종료
reverse.next = 3;  // reverse 5->4->3->2->1 (->null)

return reverse;   // reverse  5->4->3->2->1

0개의 댓글