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

11649 단어 데이터 구조
링크 에서 주어진 값 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;
        }
    }
    }
    
    

    좋은 웹페이지 즐겨찾기