데이터 구조 - 링크 요소 제거 (자바 언어 기반)

링크 에서 주어진 값 val 과 같은 모든 노드 를 삭제 합 니 다.예시:

  : 1->2->6->3->4->5->6, val = 6
  : 1->2->3->4->5

방법 1: 사상: 원 링크 의 모든 노드 를 옮 겨 다 니 며 각 노드 의 val 값 을 비교 하고 val 값 과 같 지 않 은 노드 를 하나씩 새로운 링크 에 삽입 합 니 다. val 값 과 같 지 않 은 노드 를 만 날 때마다 이 노드 를 새로운 링크 에 삽입 하고 꼬리 삽입 이 필요 합 니 다.구체 적 인 실현:

변 수 를 정의 합 니 다 (1) 원 링크 에 머리 노드 head 가 있 습 니 다. 하나의 cur 변 수 를 정의 하여 현재 변 수 를 표시 하고 cur = head 를 정의 합 니 다.(2) 결 과 를 저장 하기 위해 새로운 링크 result 를 정의 합 니 다.(3) 원래 의 링크 에서 val 값 과 같 지 않 은 노드 는 결과 링크 를 삽입 해 야 한다. 끝 에 꽂 을 때 결과 링크 의 마지막 노드 를 알 고 last 노드 를 정의 하여 결과 링크 의 마지막 노드 를 기록 해 야 한다.

원 링크 를 옮 겨 다 니 는 조건: cur! =null 원 링크 는 옮 겨 다 니 는 과정 에서 노드 를 증진 시 킵 니 다. cur = cur. next (2) 옮 겨 다 니 는 과정 에서 줄 끝 에 i 를 삽입 합 니 다. 현재 노드 끝 을 결과 링크 에 삽입 하면 현재 노드 는 결과 링크 의 마지막 노드 입 니 다. cur. next = null;ii. 결과 링크 를 정의 할 때 빈 것 으로 정의 합 니 다.결과 링크 에 노드 를 처음 삽입 하면 머리 노드 를 지정 합 니 다. result = cur;last = cur 결과 링크 가 비어 있 지 않 을 때 last. next = cur;그리고 마지막 노드 를 업데이트 합 니 다: last = cur;

결과 링크 되 돌려 주기: return result;

코드 구현:

package www.fanfan.com;

/**
 * author:kelly_fanfan
 */
public class leetCode203 {
     

     public class ListNode {
     
      int val;
     ListNode next;
     ListNode(int x) {
     
         val = x;
     }
  }

    class Solution {
     
        public ListNode removeElements(ListNode head, int val) {
     
            //1.     
            ListNode cur = head;//      
            ListNode result = null;//      
            ListNode last = null;//        
            //2.   
            while(cur != null){
     
                ListNode next = cur.next;

                if(cur.val != val){
     
                    //  
                    //    cur       ，              ，  。cur.next = null
                    cur.next = null;
                    if(result == null){
     
                        result = cur;
                    }else{
     
                        last.next = cur;
                    }
                    //             
                    //     last = cur                 
                    last = cur;
                }
                cur = next;
            }
            return result;
        }
    }
}

방법 2: 사상: 원 링크 를 옮 겨 다 니 며 각 노드 의 val 값 과 주어진 val 값 을 비교 하고 같 으 면 이 노드 를 직접 삭제 하고 옮 겨 다 니 며 계속 내 려 갑 니 다.마지막 으로 얻 은 링크 는 val 값 과 같은 노드 의 링크 를 모두 삭제 하 는 것 이다.난점: 한 노드 를 삭제 하려 면 이 노드 의 앞 노드 를 알 아야 합 니 다.그러나 머리 결 점 전에는 노드 가 없 기 때문에 머리 결 점 의 상황 을 특별히 고려 해 야 한다.
코드 구현:

package www.fanfan.com;

/**
 * author:kelly_fanfan
 */
public class leetCode203 {
     

     public class ListNode {
     
      int val;
     ListNode next;
     ListNode(int x) {
     
         val = x;
     }
  }
class Solution {
     
    public ListNode removeElements(ListNode head, int val) {
     
        if(head == null){
     
            return null;
        }
        while(head.val == val){
     
            head = head.next;
            if(head == null){
     
                return null;
            }
        }
        ListNode cur = head;
        
        while(cur.next != null){
     
            if(cur.next.val == val){
     
                cur.next = cur.next.next;
            }else{
     
                cur = cur.next;
            }
            
        }
        return head;
    }
}
}