[LeetCode] 83 - Remove Duplicates from Sorted List

https://jiwon-jjw.github.io/algorithm/2021/01/13/LeetCode83.html

LeetCode 83 - Remove Duplicates from Sorted List | Study Blog

 

 

[Java] Leetcode 83 - Remove Duplicates from Sorted List

• 문제 링크

• 나의 답:

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

• 노드의 삭제와 비슷한 문제였던 것 같다. 그림으로 설명 하자면, 다음과 같다.
  1. 아래와 같은 예시가 있다. 이는
  2. ListNode head 에 들어온 값이다. 
  3. 처음에 다음과 같은 코드를 입력하여, prev값과, cur 값을 지정해주었다.이를 그림으로 표현하자면, 다음과 같다. 

  4. ListNode prev = head;
     ListNode cur = head.next;
     

  5. 그러나 살펴보니, prev의 값 1과 cur의 값 1이 서로 같다. 위의 코드에서 반복문을 살펴보면, 서로 값이 같을 경우, 중복값을 제외하라고 나타나있다.만일 값이 같을경우, prev의 다음 참조 값은, cur의 다음 참조값을 참조하라고 나타나 있다. 이를 그림으로 옮겨보면 다음과 같다.
  6. 

  7. if(cur.val == prev.val){ // 여기서 val이 위의 그림으로 따지면 1에 해당된다.
             prev.next = cur.next;
             cur = prev;
           }
     

  8. 또, 다음 줄에 cur은 prev이 현재 참조하고 있는 값을 가지도록 나타나있다.
  9. cur = prev; 때문에, 현재 cur이 있던 위치는, prev과 같아지게 된다. 
  10. 그 다음 줄들을 살펴보면,이라고 작성되어있다. 현재 cur의 참조 위치는 prev과 같으니, prev은 이동이 없고 cur은 cur의 다음 참조 변수. 즉, 이전에 지정했던 2에 해당된다. (포인터가 이미 2로 옮겨갔기 때문에!) 

  11. prev = cur;
      cur = cur.next;
      

  12. prev의 값과, cur의 값은 서로 다르다. 그러니, 한 번 더 반복문이 실행되어 다음 값을 가리키게 된다.
  13. prev은 cur있던 자리, cur은 자신이 있던 자리가 참조하고 있는 다음 값으로! 
  14. 6번 또한 중복값이 없으므로, 한 번 더 반복문이 실행된다. 
  15. 이번엔 값이 중복되고 있다. 3번에서 실행되었던 조건문이 실행되어, 다음과 같이 prev의 포인터가 cur의 다음 값을 참조하게 된다. 
  16. 또한, 조건문을 빠져나오기 전, 4번과 같은 형태로 돌아가게 된다. 
  17. 또 한번 반복문이 진행 될 경우, cur = cur.next; 는, null이 되니, 반복문은 종료가 되고 값은 저장이 되어, head를 리턴하면 위와 같은 LinkedList를 얻을 수 있다.
  • LinkedList는 참조값의 포인터들을 모두 옮겨놓은 것이기 때문에, 위의 코드에서 head를 직접적으로 언급한 것은 prev과 cur의 값을 지정한 것 뿐이지만, head자체에도 저장이 된다.
  • 또, 사실 위에서 표현하지 않았지만, 실제로 값을 살펴보면 밑으로 빠진 중복값도 아래의 그림처럼 포인터가 다음 값을 향하게 된다. 
• 결과: